Go language problem solution LeetCode724 finds the center subscript of the array

Question description

724. Find the center subscript of the array - LeetCode ()

Give you an array of integersnums, please calculate the array'sCenter subscript 。

ArrayCenter subscriptis a subscript of an array, and the sum of all elements on the left is equal to the sum of all elements on the right.

If the center subscript is at the leftmost end of the array, the sum of the left-side numbers is considered0, because there is no element to the left of the subscript. This also applies to the center subscript at the rightmost end of the array.

If the array has multiple center subscripts, it should returnClosest to the leftThe one. If the array does not have a central subscript, return -1.

Example 1:

enter：nums = [1, 7, 3, 6, 5, 6]
Output：3
explain：
The center subscript is 3 。
The sum of the numbers on the left sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
The sum of the numbers on the right sum = nums[4] + nums[5] = 5 + 6 = 11 ，The two are equal。

Example 2:

enter：nums = [1, 2, 3]
Output：-1
explain：
There is no central subscript in the array that meets this condition。

Example 3:

enter：nums = [2, 1, -1]
Output：0
explain：
The center subscript is 0 。
The sum of the numbers on the left sum = 0 ，（Subscript 0 No element exists on the left），
The sum of the numbers on the right sum = nums[1] + nums[2] = 1 + -1 = 0 。

hint:

1 <= <= 10^4

-1000 <= nums[i] <= 1000

Idea Analysis

Brutality Cracking Ideas: traverse each bit of the array, calculate all the values on the left and all the values on the right of each bit, and then compare. The complexity is O(n²);

Optimize brute force crack

In fact, when traversing, there is no need to calculate all the values every time. We can use the calculated values for the last time to increase or decrease one by one to get the target value of this time.

[1, 2, 3 ,4 ,5, 6]

Traversal 1: The current bit is 1, leftSum[0]=0, rightSum[0]=20;

Traversal 2: The current bit is 2, leftSum[1]=leftSum[0]+nums[0] = 1, rightSum[1] = rightSum[0] - nums[1] = 18;

Traversal 3: The current bit is 3, leftSum[2]=leftSum[1]+nums[1] = 3, rightSum[2] = rightSum[1] - nums[2] = 15;

........

AC Code

class Solution {
    public int pivotIndex(int[] nums) {
        int length = ;
        if (length == 0) {
            return -1;
        }
        if (length == 1) {
            return 0;
        }
        // The accumulated value on the left and right sides, initialization        int leftSum = 0;
        int rightSum = 0;
        // Right accumulated value, starting from the second position to the last position        for (int i=1;i&lt;length;i++) {
            rightSum += nums[i];
        }
        for (int i=0;i&lt;length;i++) {
            if (i == 0) {
                if (leftSum == rightSum) {
                    return i;
                }
            } else {
                // It is not the first digit. The accumulated value of the left must be added with the previous digit. The accumulated value of the right must be subtracted with the original digit.                leftSum += nums[i-1];
                rightSum -= nums[i];
                if (leftSum == rightSum) {
                    return i;
                }
            }
        }
        return -1;
    }
}

The above is the detailed content of the Go language problem solving LeetCode724 searching for the center subscript of the array. For more information on finding the center subscript of the array in Go language, please pay attention to my other related articles!