当前位置：首页 > news >正文

LeetCode 724：寻找数组的中心下标 | 前缀和的平衡点

news 2026/5/24 4:19:42

LeetCode 724：寻找数组的中心下标 | 前缀和的平衡点

引言

寻找数组的中心下标（Find Pivot Index）是 LeetCode 第 724 题，难度为 Easy。题目要求在数组中找到某个索引，使得该索引左侧所有元素的和等于右侧所有元素的和。如果存在这样的索引，返回它；如果不存在，返回 -1。

这道题虽然是简单难度，但蕴含了前缀和思想的精髓。通过预先计算前缀和，我们可以在 O(n) 时间内找到中心下标。本文将详细分析这个问题及其扩展应用。

问题分析

题目描述

给定一个整数数组 nums，计算并返回数组的"中心索引"。如果存在中心索引 i，则满足 nums[0] + nums[1] + ... + nums[i-1] == nums[i+1] + nums[i+2] + ... + nums[n-1]。如果中心索引位于数组的最左端，则左侧总和为 0，同样的定义也适用于数组的最右端。如果不存在中心索引，返回 -1。

例如，输入 nums = [1, 7, 3, 6, 5, 6]，输出为 3，因为索引 3 左侧的元素和为 1+7+3=11，右侧的元素和为 5+6=11。输入 nums = [1, 2, 3]，输出为 -1，因为不存在满足条件的中心索引。

问题特点

这道题的关键挑战是如何高效地计算每个索引左侧和右侧的元素和。如果对每个索引都重新计算左右和，时间复杂度为 O(n²)。通过使用前缀和，我们可以将每个索引的左右和计算优化到 O(1)，总时间复杂度为 O(n)。

解决方案

前缀和优化

def pivotIndex(nums): total_sum = sum(nums) left_sum = 0 for i in range(len(nums)): if left_sum == total_sum - left_sum - nums[i]: return i left_sum += nums[i] return -1

这个方法首先计算数组的总和。然后遍历数组，维护一个变量 left_sum 表示当前索引左侧的元素和。对于索引 i，右侧的元素和等于 total_sum - left_sum - nums[i]。如果 left_sum 等于这个值，说明 i 是中心索引。

详细解析

初始化 total_sum = sum(nums)，计算整个数组的元素和。初始化 left_sum = 0，表示索引 0 左侧没有元素。

遍历到索引 i 时，首先检查 left_sum == total_sum - left_sum - nums[i] 是否成立。如果成立，说明索引 i 的左右和相等，返回 i。然后更新 left_sum += nums[i]，为下一次检查做准备。

如果遍历结束都没有找到中心索引，返回 -1。

算法正确性证明

中心索引的定义

对于索引 i，如果它是中心索引，则满足：
sum(nums[0:i]) = sum(nums[i+1:n])

其中 sum(nums[0:i]) 表示 nums[0] 到 nums[i-1] 的和，sum(nums[i+1:n]) 表示 nums[i+1] 到 nums[n-1] 的和。

正确性分析

在遍历到索引 i 时，left_sum 正好等于 sum(nums[0:i])，因为 left_sum 在遍历过程中逐步累加每个元素。total_sum - left_sum - nums[i] 正好等于 sum(nums[i+1:n])，因为 total_sum 是所有元素之和，减去 left_sum（左侧之和）和 nums[i]（当前元素）后，就是右侧之和。

因此，条件 left_sum == total_sum - left_sum - nums[i] 与中心索引的定义等价。

复杂度分析

时间复杂度

时间复杂度为 O(n)，因为我们首先用一次遍历计算总和，然后第二次遍历查找中心索引。虽然有两个遍历，但总体仍然是线性的。

空间复杂度

空间复杂度为 O(1)，只使用了常数个额外变量。

代码实现

Python 实现

def pivotIndex(nums): total_sum = sum(nums) left_sum = 0 for i in range(len(nums)): if left_sum == total_sum - left_sum - nums[i]: return i left_sum += nums[i] return -1

Java 实现

public int pivotIndex(int[] nums) { int totalSum = 0; for (int num : nums) { totalSum += num; } int leftSum = 0; for (int i = 0; i < nums.length; i++) { if (leftSum == totalSum - leftSum - nums[i]) { return i; } leftSum += nums[i]; } return -1; }

边界情况处理

空数组

当数组为空时，不存在中心索引，应该返回 -1。代码中，total_sum = 0，循环不会执行，返回 -1。

单个元素

当数组只有一个元素时，该元素是中心索引，因为左侧和右侧都是 0。例如 nums = [10]，输出应为 0。代码中，total_sum = 10，left_sum = 0，检查 i = 0 时，条件为 0 == 10 - 0 - 10 = 0，成立，返回 0。

全相同元素

例如 nums = [1, 1, 1, 1]，中心索引可能是 1 或 2。代码会返回第一个满足条件的索引。

无中心索引

例如 nums = [1, 2, 3]，没有任何索引满足左右和相等，代码返回 -1。

全零数组

例如 nums = [0, 0, 0, 0]，任何索引都可能满足条件。代码会返回第一个满足条件的索引，即 0。

测试用例

def test_pivot_index(): assert pivotIndex([1, 7, 3, 6, 5, 6]) == 3 assert pivotIndex([1, 2, 3]) == -1 assert pivotIndex([2, 1, -1]) == 0 assert pivotIndex([1, -1, 2, -2]) == 2 assert pivotIndex([0, 0]) == 0 assert pivotIndex([0, 0, 0, 0]) == 0 assert pivotIndex([]) == -1 assert pivotIndex([10]) == 0 print("所有测试用例通过！")

扩展问题

返回所有中心索引

如果题目要求返回所有中心索引，而不是第一个，可以收集所有满足条件的索引后返回列表：

def allPivotIndices(nums): total_sum = sum(nums) left_sum = 0 result = [] for i in range(len(nums)): if left_sum == total_sum - left_sum - nums[i]: result.append(i) left_sum += nums[i] return result