刷题之旅从数组类型的题目开始。第三十四道题目是寻找数组的中心索引,对应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%的用户