leetcode：724. Find the central subscript of the array

Title source

• leetcode：724. Find the central subscript of the array
• leetcode：1991. Find the central subscript of the array

Title Description

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

    }
};

title

violence

Ideas ： Find subscript i All previous elements （ barring i） And , And subscripts i And then all the elements （ barring i） And , Compare whether they are equal , If equal, it means i It's the middle position , Then return to i. If none of them match, it returns -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) {
    
    	 //  Loop through all elements in the array 
        for (int i = 0; i < nums.size(); ++i) {
    
        	 //  Calculate subscript i The sum of all elements before and after 
            int before = beforeSum(nums, i);
            int after = afterSum(nums, i);
            //  If equal, return i
            if(before == after){
    
                return i;
            }
        }
        return -1;
    }
};

The prefix and

Ideas ： If a subscript i If the prefix sum of is equal to its suffix sum, it means that the middle position of the array is found . The prefix and are i The sum of all previous elements , The suffix and are i Then the sum of all the elements , Not including i

class Solution {
    
public:
    int pivotIndex(vector<int>& nums) {
    
        //  Calculation nums The sum of all elements in the array 
        int sum = 0;
        for (int num : nums) {
    
            sum += num;
        }
        
        int preSum = 0; //  The prefix and 
        for (int i = 0; i < nums.size(); ++i) {
    
            //  Suffixes and , That is, the sum of array elements minus the prefix and , Subtract the current element to get the result 
            int postSum = sum - preSum - nums[i];
            if(preSum == postSum){
    
                return i;
            }
             //  Update prefix and 
            preSum += nums[i];
        }
        return -1;
    }
};

The prefix and

• because ： The prefix and + nums[i] + Suffixes and = The sum of the
• also ： Request to find 【 The prefix and == Suffixes and 】
• therefore ： 2 * The prefix and = The sum of the - nums[i]

class Solution {
    
public:
    int pivotIndex(vector<int>& nums) {
    
        //  Calculation nums The sum of all elements in the array 
        int sum = 0;
        for (int num : nums) {
    
            sum += num;
        }
        
        int preSum = 0; //  The prefix and 
        for (int i = 0; i < nums.size(); ++i) {
    
            //  The prefix and  + nums[i] +  Suffixes and  =  The sum of the 
            // if( The prefix and == Suffixes and ) return i;
            //  therefore ：if(2* The prefix and = The sum of the -nums[i]) return i;
            if(2 * preSum == sum - nums[i]){
    
                return i;
            }
            //  Update prefix and 
            preSum += nums[i];
        }
        return -1;
    }
};