刷题之旅从数组类型的题目开始。第三十四道题目是寻找数组的中心索引，对应leetcode的题号为724。

image

题目描述

给定一个整数类型的数组 nums，请编写一个能够返回数组“中心索引”的方法。

我们是这样定义数组中心索引的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。

如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。

示例 1:

1
2
3
4
5
6
输入: 
nums = [1, 7, 3, 6, 5, 6]
输出: 3
解释: 
索引3 (nums[3] = 6) 的左侧数之和(1 + 7 + 3 = 11)，与右侧数之和(5 + 6 = 11)相等。
同时, 3 也是第一个符合要求的中心索引。

示例 2:

1
2
3
4
5
输入: 
nums = [1, 2, 3]
输出: -1
解释: 
数组中不存在满足此条件的中心索引。

说明:

  • nums 的长度范围为 [0, 10000]。
  • 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。

解题思路

最简单的思路一定是遍历数组，不断计算左右两边的元素和，一旦相等就结束，返回索引，这个索引就是符合条件的最左边的索引。具体见代码注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int pivotIndex(int[] nums) {
        // 从左向右遍历数据，求解元素【左边左右元素】之和以及【右边所有元素之和】
        // 注意特殊情况，比如[-1,-1,-1,0,1,1]，那么此时程序应该返回0，因为第一元素后面所有元素和为0，第一个元素的左边没有元素，默认为0
        // 那么就要考虑边界问题，从第0个元素出发的时候，左边的sum一开始必然为0
        // 当移动到最后一个元素的时候，右边的sum也必然为0，这两个特殊情况直接在sum函数中进行了单独处理
        for(int i=0;i<nums.length;i++){
            if(sum(nums,0,i-1) == sum(nums,i+1,nums.length-1)){
                return i;
            }
        }
        return -1;
    }

    private int sum(int[] nums,int start,int end){
        int res = 0;
        // 第一个元素左边没有元素，直接返回0即可
        if(end < 0){
            return 0;
        }
        // 最后一个元素右边没有元素，直接返回0即可
        if(start == nums.length){
            return 0;
        }
        // 两边都有元素的时候，正常计算即可
        for(int i=start;i<=end;i++){
            res += nums[i];
        }
        return res;
    }
}
1
2
3
执行结果：通过 显示详情
执行用时 :576 ms, 在所有 Java 提交中击败了5.06%的用户
内存消耗 :42.7 MB, 在所有 Java 提交中击败了30.37%的用户

双层for循环，时间复杂度为O(n^2)，空间复杂度为O(1)。效率太低，着手进行优化。

想到的第二个优化思路为：其实我没必要同时计算左边和以及右边和，只需要计算左边和即可，因为我很容易能计算出数组的所有元素和，那么就很好计算出所谓中心索引两边的和应该是多少，那么我只要去判断这两个和是否相等即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        for(int i=0;i<nums.length;i++){
            // 计算剔除当前元素后，两边和如何相等，那么应该等于什么值
            // 这个值必须是整数，因为我们这里是整数数组，如果都不是整数了，那肯定加不出来这个值，直接continue掉计算下一个
            if((sum-nums[i])%2 != 0){
                continue;
            }
            int midSumValue = (sum-nums[i])/2;
            int temp = 0;
            // 这个时候只需要计算左边的元素即可
            for(int j=0;j<i;j++){
                temp += nums[j];
            }
            if(temp == midSumValue){
                return i;
            }
        }
        return -1;
    }
}
1
2
3
执行结果：通过 显示详情
执行用时 :97 ms, 在所有 Java 提交中击败了25.64%的用户
内存消耗 :42.8 MB, 在所有 Java 提交中击败了30.37%的用户

嗯，效率已经提高了很多了，但是总体上的效果不尽人意，还要提升！刚才的一个思路是：先求和sum，然后剔除当前元素nums[i]，然后除以2，得到应该等于的值叫midSumValue ，计算当前元素i之前所有元素之和是否等于midSumValue 。

那么其实这里是可以做优化的，没必要每次起一个for循环去计算i左边所有元素的和：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        // 这个temp就是代表i左边所有元素的值
        int temp = 0;
        for(int i=0;i<nums.length;i++){
            // 计算剔除当前元素后，两边和如何相等，那么应该等于什么值
            // 这个值必须是整数，因为我们这里是整数数组，如果都不是整数了，那肯定加不出来这个值，直接continue掉计算下一个
            if((sum-nums[i])%2 != 0){
                temp += nums[i];
                continue;
            }
            int midSumValue = (sum-nums[i])/2;
            if(temp == midSumValue){
                return i;
            }
            temp += nums[i];
        }
        return -1;
    }
}

时间复杂度已经降到了O(n)，执行效果：

1
2
3
执行结果：通过 显示详情
执行用时 :2 ms, 在所有 Java 提交中击败了82.52%的用户
内存消耗 :42.5 MB, 在所有 Java 提交中击败了30.37%的用户

总感觉代码有点冗余，那么能不能反过来想呢，即【左边元素求和*2+当前元素的值】，如果等于sum，不就是表示当前元素满足这个中心索引的要求么。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for(int i=0;i<nums.length;i++){
            sum += nums[i];
        }
        int temp = 0;
        for(int i=0;i<nums.length;i++){
            // 先根据【左边元素求和*2+当前元素的值】计算等不等于sum
            if(temp*2+nums[i] == sum){
                return i;
            }
            // 再对temp进行调整，因为要保证temp的值是i之前的元素，当i=0的时候，temp就应该是0；当i=1的时候，temp=nums[0]
            temp += nums[i];
        }
        return -1;
    }
}

代码简洁了很多，因为乘法代替除法减少了一步是否为小数的判断。运行效果基本一致：

1
2
3
执行结果：通过 显示详情
执行用时 :2 ms, 在所有 Java 提交中击败了82.52%的用户
内存消耗 :42.5 MB, 在所有 Java 提交中击败了30.37%的用户