This is the 1st / 100th question that I insist on swiping the card~

 

1, Title Description

Give you an integer array nums, please calculate the central subscript of the array.

The central subscript of the array is a subscript of the array. The sum of all elements on the left is equal to the sum of all elements on the right.

If the central subscript is at the leftmost end of the array, the sum of the numbers on the left is regarded as 0 because there is no element to the left of the subscript. The same applies when the central subscript is at the right most end of the array.

If the array has multiple central subscripts, the one closest to the left should be returned. Returns - 1 if the array does not have a central subscript.

Example 1:

Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
 Explanation:
The center subscript is 3.
Sum of left numbers sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
Sum of right numbers sum = nums[4] + nums[5] = 5 + 6 = 11 ，They are equal.

Example 2:

Input: nums = [1, 2, 3]
Output:-1
 Explanation:
There is no central subscript in the array that meets this condition.

Example 3:

Input: nums = [2, 1, -1]
Output: 0
 Explanation:
The center subscript is 0.
Sum of left numbers sum = 0 ，(There is no element to the left of subscript 0),
Sum of right numbers sum = nums[1] + nums[2] = 1 + -1 = 0 . 

Tips:
  1 <= nums.length <= 10^4
  -1000 <= nums[i] <= 1000

 

Author: leetcode
Link: https://leetcode-cn.com/leetbook/read/array-and-string/yf47s/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

2, Topic analysis

Idea:
Comment directly in the code!

3, Code

1.C implementation

My implementation method:

It is divided into two parts:
Part I: calculate the sum of all elements in the array except the leftmost element, and record it as rsum;
Part 2: for loop traverses the array from subscript 1 to the end to judge whether rsum is equal to lsum.

int pivotIndex(int* nums, int numsSize){
	int rsum = 0; int lsum = 0;
	for(int i = 1;i<numsSize;i++)
		rsum += nums[i];
	if(0 == rsum)
		return 0;
	
	for(int i=1;i<numsSize;i++)
	{
		rsum -= nums[i];
		lsum += nums[i-1];
		if(rsum == lsum)
			return i;
	}
    return -1;
}

Advanced method:

Note that the sum of all elements of the array is total. When traversing the ith element, set the sum of the left elements as sum, and the sum of the right elements as total numsi sum. The left and right elements are equal, that is sum = total numsi sum, that is 2Xsum+numsi=total.
When there are no elements on the left or right side of the central index, zero items are added, which is mathematically called [empty sum]. In programming, we agree that [null and zero].
 

Author: leetcode solution
Link: https://leetcode-cn.com/problems/find-pivot-index/solution/xun-zhao-shu-zu-de-zhong-xin-suo-yin-by-gzjle/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

int pivotIndex(int* nums, int numsSize) {
    int total = 0;
    for (int i = 0; i < numsSize; ++i) {
        total += nums[i];
    }
    int sum = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (2 * sum + nums[i] == total) {
            return i;
        }
        sum += nums[i];
    }
    return -1;
}

2.C + + implementation

Realize the above advanced method.

class Solution {
public:
    int pivotIndex(vector<int> &nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);
        int sum = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return -1;
    }
};

3.Python implementation

In fact, the above advanced method is still used, but this article talks about the preview method in depth. You can take a closer look:
Author: fuxuemingzhu
Link: https://leetcode-cn.com/problems/find-pivot-index/solution/xiang-jie-presumhao-de-ti-jie-ying-gai-k-mzsg/
Source: LeetCode
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        N = len(nums)
        sums_ = sum(nums)
        preSum = 0
        for i in range(N):
            if preSum == sums_ - preSum - nums[i]:
                return i
            preSum += nums[i]
        return -1