leetcode：724. 寻找数组的中心下标

题目来源

• leetcode：724. 寻找数组的中心下标
• leetcode：1991. 寻找数组的中心下标

题目描述

class Solution {
    
public:
    int pivotIndex(vector<int>& nums) {
    

    }
};

题目解析

暴力

思路：求下标i之前所有元素（不包括i）的和，以及下标i之后所有元素（不包括i）的和，比较二者是否相等，如果相等则表示i是中间位置，则返回i。如果所有都不能匹配则返回-1。

class Solution {
    
    int beforeSum(vector<int>& nums, int idx){
    
        int sum = 0;
        for (int i = 0; i < idx; ++i) {
    
            sum += nums[i];
        }
        return sum;
    }
    int afterSum(vector<int>& nums, int idx){
    
        int sum = 0;
        for (int i = nums.size() - 1; i > idx; --i) {
    
            sum += nums[i];
        }
        return sum;
    }
public:
    int pivotIndex(vector<int>& nums) {
    
    	 // 循环遍历数组中所有元素
        for (int i = 0; i < nums.size(); ++i) {
    
        	 // 计算下标i之前和之后所有元素的总和
            int before = beforeSum(nums, i);
            int after = afterSum(nums, i);
            // 如果相等则返回i
            if(before == after){
    
                return i;
            }
        }
        return -1;
    }
};

前缀和

思路：如果某下标i的前缀和与其后缀和相等则表示找到了数组的中间位置。前缀和就是i之前所有元素的总和，后缀和就是i之后所有元素的总和，都不包括i

class Solution {
    
public:
    int pivotIndex(vector<int>& nums) {
    
        // 计算nums数组的中所有元素总和
        int sum = 0;
        for (int num : nums) {
    
            sum += num;
        }
        
        int preSum = 0; // 前缀和
        for (int i = 0; i < nums.size(); ++i) {
    
            // 后缀和，即数组元素总和减去前缀和，减去当前元素得到的结果
            int postSum = sum - preSum - nums[i];
            if(preSum == postSum){
    
                return i;
            }
             // 更新前缀和
            preSum += nums[i];
        }
        return -1;
    }
};

前缀和

• 因为： 前缀和 + nums[i] + 后缀和 = 总和
• 又：要求找到 【前缀和 == 后缀和】
• 所以： 2 * 前缀和 = 总和 - nums[i]

class Solution {
    
public:
    int pivotIndex(vector<int>& nums) {
    
        // 计算nums数组的中所有元素总和
        int sum = 0;
        for (int num : nums) {
    
            sum += num;
        }
        
        int preSum = 0; // 前缀和
        for (int i = 0; i < nums.size(); ++i) {
    
            // 前缀和 + nums[i] + 后缀和 = 总和
            // if(前缀和==后缀和) return i;
            // 所以：if(2*前缀和=总和-nums[i]) return i;
            if(2 * preSum == sum - nums[i]){
    
                return i;
            }
            // 更新前缀和
            preSum += nums[i];
        }
        return -1;
    }
};