寻找数组的中心下标
难度:
标签:
题目描述
English description is not available for the problem. Please switch to Chinese.
代码结果
运行时间: 30 ms, 内存: 16.9 MB
/*
* 思路:
* 1. 使用Java Stream计算数组的总和。
* 2. 使用普通循环迭代数组,并计算左侧元素的和。
* 3. 比较左侧元素的和和总和减去左侧和再减去当前元素值,如果相等则返回当前下标。
* 4. 如果未找到,返回-1。
*/
import java.util.stream.IntStream;
public class Solution {
public int pivotIndex(int[] nums) {
int totalSum = IntStream.of(nums).sum();
int leftSum = 0;
for (int i = 0; i < nums.length; i++) {
if (leftSum == totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}
}
解释
方法:
这个题解首先计算整个数组的总和,存储在变量 all_sum 中。然后遍历数组,使用一个变量 pre_sum 来记录当前索引左侧的元素和。在每次循环中,检查当前索引 i 是否是中心下标,即检查除去当前元素 nums[i] 后的剩余元素和是否为 2 倍的 pre_sum(即两侧相等)。如果是,则返回当前索引。如果遍历结束还没有找到符合条件的中心下标,则返回 -1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在检查中心下标时,条件是 `all_sum - nums[i] - pre_sum == pre_sum` 而不是直接比较左右两边的和?
▷🦆
在整个算法中,是否存在对数组中的负数或零的特殊处理,或者这些情况会怎样影响算法的执行?
▷🦆
在算法执行中,如果数组只有一个元素,此时算法会返回什么结果?是否符合预期的中心下标定义?
▷