leetcode
leetcode 2901 ~ 2950
寻找数组的中心下标

寻找数组的中心下标

难度:

标签:

题目描述

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` 而不是直接比较左右两边的和?
这个条件是基于中心下标左侧和右侧的和必须相等的原则。假设 `pre_sum` 是中心下标左侧元素的总和。右侧元素的总和可以表示为 `all_sum - nums[i] - pre_sum`,其中 `all_sum` 是数组的总和,`nums[i]` 是中心下标处的值。因此,如果左侧和等于右侧和,即 `pre_sum == all_sum - nums[i] - pre_sum`,则说明找到了中心下标。直接比较左右两边的和需要额外的变量来记录右侧和,而使用这种方式可以简化计算和空间复杂度。
🦆
在整个算法中,是否存在对数组中的负数或零的特殊处理,或者这些情况会怎样影响算法的执行?
算法中没有对负数或零进行特殊处理,因为算法逻辑本身适用于包括负数和零在内的任何整数。总和 `all_sum` 和前缀和 `pre_sum` 都会自然地计算这些值。负数和零的存在不会影响算法的正确性,因为算法只是基于数学上的总和来判断,并不依赖于元素的具体值。
🦆
在算法执行中,如果数组只有一个元素,此时算法会返回什么结果?是否符合预期的中心下标定义?
如果数组只有一个元素,那么这个元素的索引为0。在这种情况下,`pre_sum` 为0(因为没有左侧元素),右侧也没有元素,所以 `all_sum - nums[0]` 也为0。这满足条件 `all_sum - nums[0] - pre_sum == pre_sum`。因此,算法会返回0,这是符合中心下标的定义的,因为左侧和右侧的元素之和都是0。

相关问题