寻找数组的中心下标
难度:
标签:
题目描述
代码结果
运行时间: 53 ms, 内存: 16.8 MB
/*
* Problem: Find the pivot index using Java Streams.
* Approach:
* 1. Calculate the total sum of the array using streams.
* 2. Iterate through the array, maintaining a running left sum.
* 3. For each element, check if the left sum equals the total sum minus the left sum minus the element.
* 4. If such an element is found, return its index; otherwise, return -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;
}
}
解释
方法:
这个题解的思路是先计算整个数组的总和 sum,然后遍历数组,在遍历过程中维护一个变量 left 表示当前下标左侧元素之和。对于每个下标 i,判断 left 的两倍加上 nums[i] 是否等于总和 sum,如果相等则说明 i 是中心下标,直接返回 i。如果遍历结束都没有找到中心下标,则返回 -1。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中,为什么需要判断`left * 2 + nums[i] == all`来确定中心下标?这个条件是怎样得出的?
▷🦆
如果数组中包含负数,这种方法是否依然有效?是否需要考虑负数对总和和左侧和的影响?
▷🦆
为什么在没有找到满足条件的中心下标时,算法的返回值是`-1`?这种设计有什么特别的意义吗?
▷🦆
这个算法在所有情况下都能正确返回最靠左的中心下标吗?存在哪些可能的边界情况需要特别注意?
▷