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

LeetCode 724寻找数组的中心下标 | 前缀和的平衡点引言寻找数组的中心下标Find Pivot Index是 LeetCode 第 724 题难度为 Easy。题目要求在数组中找到某个索引使得该索引左侧所有元素的和等于右侧所有元素的和。如果存在这样的索引返回它如果不存在返回 -1。这道题虽然是简单难度但蕴含了前缀和思想的精髓。通过预先计算前缀和我们可以在 O(n) 时间内找到中心下标。本文将详细分析这个问题及其扩展应用。问题分析题目描述给定一个整数数组 nums计算并返回数组的中心索引。如果存在中心索引 i则满足 nums[0] nums[1] ... nums[i-1] nums[i1] nums[i2] ... nums[n-1]。如果中心索引位于数组的最左端则左侧总和为 0同样的定义也适用于数组的最右端。如果不存在中心索引返回 -1。例如输入 nums [1, 7, 3, 6, 5, 6]输出为 3因为索引 3 左侧的元素和为 17311右侧的元素和为 5611。输入 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[i1:n])其中 sum(nums[0:i]) 表示 nums[0] 到 nums[i-1] 的和sum(nums[i1:n]) 表示 nums[i1] 到 nums[n-1] 的和。正确性分析在遍历到索引 i 时left_sum 正好等于 sum(nums[0:i])因为 left_sum 在遍历过程中逐步累加每个元素。total_sum - left_sum - nums[i] 正好等于 sum(nums[i1: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 -1Java 实现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 10left_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中心下标的变体在某些变体中可能要求左右和的绝对值相等或者要求左右和的乘积相等。核心思路类似都是利用前缀和来快速计算左右和。实际应用场景寻找中心下标的问题在现实中有很多应用。在物理学中可以用来寻找杜杆的支点使得左右两边的力矩相等。在经济学中可以用来寻找平衡点使得左边和右边的贡献相等。在数据分析和统计分析中可以用来寻找数据的中心类似于中位数但考虑的是元素值而非位置。从算法角度看这个问题展示了前缀和在解决平衡问题中的应用。通过预先计算总和并在遍历中动态维护左侧和我们可以在 O(n) 时间内找到平衡点。总结寻找数组的中心下标虽然是一道简单难度的题目但蕴含了前缀和思想的精髓。通过使用前缀和我们可以在 O(n) 时间和 O(1) 空间内解决这个问题。这个问题的关键洞察是利用总和和左侧和的关系可以在 O(1) 时间内计算右侧和。这种预计算遍历的思想是解决很多前缀和相关问题的基础。希望通过本文的讲解读者能够深入理解前缀和的应用并将其推广到更多类似问题的解决中。