Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

1. Title Description

Given an integer array nums, compute the central index of the array.

The central index of an array is an index of the array whose sum of the elements on the left equals the sum of the elements on the right.

If the center subscript is at the far left end of the array, the sum of the left numbers is treated as zero, because there is no element to the left of the subscript. This is also true if the center index is at the far right end of the array.

If the array has more than one central index, the one closest to the left should be returned. If the array does not have a central index, return -1.

Example 1:

Enter: nums = [1.7.3.6.5.6] output:3Explanation: The central subscript is3. Sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11Sum = nums[4] + nums[5] = 5 + 6 = 11The two are equal to each other.Copy the code

Example 2:

Enter: nums = [1.2.3] output:- 1Explanation: There is no central index in the array that satisfies this condition.Copy the code

Example 3:

Enter: nums = [2.1.- 1] output:0Explanation: The central subscript is0. Sum of the numbers on the left is equal to0, a (subscript0There is no element on the left), sum = nums[1] + nums[2] = 1 + - 1 = 0 。
Copy the code

Tip: 1 < = nums. Length < < = = 10 ^ 4-1000 nums [I] < = 1000

By LeetCode: leetcode-cn.com/leetbook/re… Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Second, the topic analysis

Direct comments in code!

Three, code,

1. C implementation

My implementation method:

There are two parts: The first part: calculate the sum of all elements except the leftmost element in the array as Rsum; Part 2: The for loop iterates through the number group from the subscript 1 to the end to determine 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;
}
Copy the code

Advanced method:

The sum of all elements in the counting group is total. When the ith element is traversed, the sum of the elements on the left is set to sum, and the sum of the elements on the right is total-numsi-sum. Sum =total-numsi-sum, that is, 2Xsum+numsi=total. When there is no element to the left or right of the central index, it is the sum of zero items, which is called the “empty sum” in mathematics. In programming we have a convention that the null sum is zero.

Author: LeetCode – Solution

Link: leetcode-cn.com/problems/fi… Copyright belongs to the author. Commercial reprint please contact the author for authorization, 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;
}
Copy the code

2. C + + implementation

Implement 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(a); ++i) {if (2 * sum + nums[i] == total) {
                return i;
            }
            sum += nums[i];
        }
        return - 1; }};Copy the code

3. The Python implementation

In fact, we still use the advanced method above, but this article is an in-depth discussion of the preSum method, you can take a closer look:

Fuxuemingzhu Link: leetcode-cn.com/problems/fi… Copyright belongs to the author. Commercial reprint please contact the author for authorization, 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
Copy the code

🔆 In The End!

This blogger will continue to update the basic column of crawler and crawler combat column, carefully read this article friends, you can like the collection and comment on your feelings after reading. And can follow this blogger, read more crawler in the days ahead!

If there are mistakes or inappropriate words can be pointed out in the comment area, thank you! If reprint this article please contact me for my consent, and mark the source and the name of the blogger, thank you!