Easy

题目描述

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

示例 1：

输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

提示：

  • 1 <= nums.length <= 10^4
  • -1000 <= nums[i] <= 1000

注意： 本题与主站 1991 题相同：https://leetcode-cn.com/problems/find-the-middle-index-in-array/

解题思路

这道题要求找到数组的中心下标，使得左侧元素之和等于右侧元素之和。

核心思路： 对于任意位置 i，如果它是中心下标，那么 left_sum = right_sum。由于 left_sum + nums[i] + right_sum = total_sum，可以推导出 left_sum = (total_sum - nums[i]) / 2。

解法一：前缀和数组

  • 创建左侧前缀和数组和右侧前缀和数组
  • 逐个比较每个位置的左右和是否相等
  • 时间复杂度 O(n)，空间复杂度 O(n)

解法二：一次遍历优化（推荐）

  • 先计算数组总和
  • 遍历数组，维护左侧和，通过总和计算右侧和
  • 当 left_sum = (total_sum - nums[i]) / 2 时，找到中心下标
  • 时间复杂度 O(n)，空间复杂度 O(1)

优化点： 避免除法运算，直接判断 2 * left_sum + nums[i] = total_sum，这样更加高效且避免浮点数精度问题。

代码实现

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        
        int leftSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (2 * leftSum + nums[i] == total) {
                return i;
            }
            leftSum += nums[i];
        }
        
        return -1;
    }
};

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        left_sum = 0
        
        for i in range(len(nums)):
            if 2 * left_sum + nums[i] == total:
                return i
            left_sum += nums[i]
        
        return -1

public class Solution {
    public int PivotIndex(int[] nums) {
        int total = nums.Sum();
        int leftSum = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (2 * leftSum + nums[i] == total) {
                return i;
            }
            leftSum += nums[i];
        }
        
        return -1;
    }
}

var pivotIndex = function(nums) {
    const total = nums.reduce((sum, num) => sum + num, 0);
    let leftSum = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (2 * leftSum + nums[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组两次：一次计算总和，一次查找中心下标
空间复杂度O(1)只使用常数级别的额外空间存储变量

相关题目