leetcode
leetcode 601 ~ 650
寻找数组的中心下标

寻找数组的中心下标

难度:

标签:

题目描述

代码结果

运行时间: 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`来确定中心下标?这个条件是怎样得出的?
这个条件基于中心下标的定义:中心下标是数组中一个特殊的位置,其左侧元素之和等于右侧元素之和。设`left`为中心下标左侧的元素之和(不包括中心下标处的元素),则中心下标右侧的元素之和也应该等于`left`。中心下标处的元素记为`nums[i]`。因此,数组的总和`all = left + nums[i] + left = 2*left + nums[i]`。由此,若要使左右两侧和相等,必须满足`left * 2 + nums[i] == all`。因此,这个条件直接反映了中心下标的定义。
🦆
如果数组中包含负数,这种方法是否依然有效?是否需要考虑负数对总和和左侧和的影响?
这种方法即使数组中包含负数也是有效的。在计算总和`all`以及左侧和`left`时, 不论元素是正数还是负数,都会按其实际值进行累加或累减。负数的存在不会影响`left * 2 + nums[i] == all`这一条件的正确性和逻辑的运行,因为这一条件只关心和的平衡,而不是具体的数值大小。
🦆
为什么在没有找到满足条件的中心下标时,算法的返回值是`-1`?这种设计有什么特别的意义吗?
在许多编程问题和算法设计中,`-1`通常被用作不存在或无效值的标志。在这个问题中,如果没有找到任何满足条件的中心下标,返回`-1`表示中心下标不存在。这种设计使得算法的返回结果具有明确的意义,便于调用者判断是否找到了有效的中心下标。
🦆
这个算法在所有情况下都能正确返回最靠左的中心下标吗?存在哪些可能的边界情况需要特别注意?
这个算法能够正确返回最靠左的中心下标。算法从数组的第一个元素开始向右遍历,第一次遇到满足`left * 2 + nums[i] == all`的下标即返回,保证了结果为最靠左的中心下标。需要特别注意的边界情况包括:数组为空时应如何处理(可能需要特别返回或处理),数组只有一个元素时(这个元素自身就是中心下标),以及所有元素都是零(任何下标都可以是中心下标)。

相关问题

和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 

子数组是数组中元素的连续非空序列。

 

示例 1:

输入:nums = [1,1,1], k = 2
输出:2

示例 2:

输入:nums = [1,2,3], k = 3
输出:2

 

提示:

  • 1 <= nums.length <= 2 * 104
  • -1000 <= nums[i] <= 1000
  • -107 <= k <= 107