signed

QiShunwang

“诚信为本、客户至上”

724. 寻找数组的中心索引

2021/1/28 13:30:41   来源:

链接:724. 寻找数组的中心索引

题解:https://leetcode-cn.com/problems/find-pivot-index/solution/xun-zhao-shu-zu-de-zhong-xin-suo-yin-by-gzjle/

时间复杂度:O(n)

空间复杂度:O(n)

class Solution {
    public:
    int pivotIndex(vector<int>& nums) {
        if(nums.size() <= 0) {
            return -1;
        }
        if(nums.size() == 1) {
            return nums[0];
        }
        // 下表i表示i左边数组的和, prefix_sum[0]=0,因为0下标左边没有数字
        vector<int> prefix_sum(nums.size(), 0);
        // 下标i表示i右边数组的和,prefix_sum[nums.size()-1]=0,因为nums.size()-1下标右边没有数字
        vector<int> back_sum(nums.size(), 0);
        for(int i = 1; i < nums.size(); ++i) {
            prefix_sum[i] = prefix_sum[i-1] + nums[i-1];
        }
        for(int i = nums.size()-2; i >= 0; --i) {
            back_sum[i] = back_sum[i+1] + nums[i+1];
        }
        // 判断左边数组和右边数组和是否相等,返回中心索引
        for(int i = 0; i < nums.size(); ++i) {
            if(prefix_sum[i] == back_sum[i]) {
                return i;
            }
        }
        return -1;
    }
};