企业官网建设流程全解析

LeetCode 724 Find Pivot Index 寻找枢轴索引：前缀和三种解法全解析（Leetcode 多语言题解）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文围绕本仓库 articles/find-pivot-index.md 讲解的LeetCode 724 Find Pivot Index（寻找数组的枢轴索引）展开：先给出暴力枚举的直观思路，再逐步推导到前缀和数组、再到常数空间的滚动前缀和最优解，并完整给出 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的可运行实现，同时对照本仓库0724-find-pivot-index.*各语言源码验证。读完本文，你将掌握前缀和思想在"左右两侧区间和相等"类问题上的应用，并能写出 O(n) 时间、O(1) 空间的面试级解法。

问题定义

给定一个整数数组nums，请计算该数组的枢轴索引（pivot index）。枢轴索引定义为：该索引左侧所有元素之和等于右侧所有元素之和的索引。

• 左侧之和指下标小于i的所有元素之和；
• 右侧之和指下标大于i的所有元素之和；
• 若i是数组最左端（i = 0），则左侧为空区间，和记为0；同理，若i是最右端，右侧空区间的和也为0；
• 如果存在多个枢轴索引，返回最左边的一个；如果不存在，返回-1。

示例

• 输入nums = [1,7,3,6,5,6]，输出3：左侧1+7+3 = 11，右侧5+6 = 11。
• 输入nums = [1,2,3]，输出-1：不存在满足条件的索引。
• 输入nums = [2,1,-1]，输出0：左侧空区间和为0，右侧1+(-1) = 0。

该题在本仓库 README 的Arrays & Hashing（数组与哈希）分类下（见 README.md），是前缀和（Prefix Sum）类问题的基础入门题，也是后续 Range Sum Query、Partition 类问题的重要铺垫。

前置知识

在动手解题前，需要掌握以下两个基础能力：

• 前缀和（Prefix Sum）：预先计算累计和数组prefixSum，使任意区间[l, r)的和可以在 O(1) 时间内求出，即sum(l, r) = prefixSum[r] - prefixSum[l]。这是本题解法二的核心工具。
• 数组遍历（Array Traversal）：在单次遍历中维护运行中的累计值（running total），配合总量减法的思想，可以在不使用额外数组的情况下完成左右两侧和的比较。这是本题解法三的核心技巧。

解法一：暴力枚举（Brute Force）

思路

最直接的想法是：依次把每个索引i当作候选枢轴，分别从零开始累加i左侧所有元素与右侧所有元素，比较两者是否相等。虽然实现简单，但每个索引都要重新扫描两侧区间，存在大量重复计算。

算法步骤

1. 遍历索引i从0到n-1；
2. 对每个i：
   • 累加下标小于i的所有元素得到leftSum；
   • 累加下标大于i的所有元素得到rightSum；
   • 若leftSum == rightSum，直接返回i；
3. 遍历结束仍未找到，返回-1。

多语言实现

class Solution: def pivotIndex(self, nums: List[int]) -> int: n = len(nums) for i in range(n): leftSum = rightSum = 0 for l in range(i): leftSum += nums[l] for r in range(i + 1, n): rightSum += nums[r] if leftSum == rightSum: return i return -1

public class Solution { public int pivotIndex(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { int leftSum = 0, rightSum = 0; for (int l = 0; l < i; l++) { leftSum += nums[l]; } for (int r = i + 1; r < n; r++) { rightSum += nums[r]; } if (leftSum == rightSum) { return i; } } return -1; } }

class Solution { public: int pivotIndex(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { int leftSum = 0, rightSum = 0; for (int l = 0; l < i; l++) { leftSum += nums[l]; } for (int r = i + 1; r < n; r++) { rightSum += nums[r]; } if (leftSum == rightSum) { return i; } } return -1; } };

class Solution { /** * @param {number[]} nums * @return {number} */ pivotIndex(nums) { const n = nums.length; for (let i = 0; i < n; i++) { let leftSum = 0, rightSum = 0; for (let l = 0; l < i; l++) { leftSum += nums[l]; } for (let r = i + 1; r < n; r++) { rightSum += nums[r]; } if (leftSum === rightSum) { return i; } } return -1; } }

public class Solution { public int PivotIndex(int[] nums) { int n = nums.Length; for (int i = 0; i < n; i++) { int leftSum = 0, rightSum = 0; for (int l = 0; l < i; l++) { leftSum += nums[l]; } for (int r = i + 1; r < n; r++) { rightSum += nums[r]; } if (leftSum == rightSum) { return i; } } return -1; } }

func pivotIndex(nums []int) int { n := len(nums) for i := 0; i < n; i++ { leftSum, rightSum := 0, 0 for l := 0; l < i; l++ { leftSum += nums[l] } for r := i + 1; r < n; r++ { rightSum += nums[r] } if leftSum == rightSum { return i } } return -1 }

class Solution { fun pivotIndex(nums: IntArray): Int { val n = nums.size for (i in 0 until n) { var leftSum = 0 var rightSum = 0 for (l in 0 until i) { leftSum += nums[l] } for (r in i + 1 until n) { rightSum += nums[r] } if (leftSum == rightSum) { return i } } return -1 } }

class Solution { func pivotIndex(_ nums: [Int]) -> Int { let n = nums.count for i in 0..<n { var leftSum = 0 var rightSum = 0 for l in 0..<i { leftSum += nums[l] } for r in (i + 1)..<n { rightSum += nums[r] } if leftSum == rightSum { return i } } return -1 } }

impl Solution { pub fn pivot_index(nums: Vec<i32>) -> i32 { let n = nums.len(); for i in 0..n { let left_sum: i32 = nums[..i].iter().sum(); let right_sum: i32 = nums[i + 1..].iter().sum(); if left_sum == right_sum { return i as i32; } } -1 } }

复杂度分析

• 时间复杂度：$O(n ^ 2)$。每个索引i都要对两侧区间各做一次 O(n) 的累加。
• 空间复杂度：$O(1)$。只使用了常数个变量。

解法二：前缀和数组（Prefix Sum）

思路

暴力法的问题在于反复重算区间和。我们可以预先构建前缀和数组，把任意区间和查询降到 O(1)。

定义prefixSum[i+1] = prefixSum[i] + nums[i]，即prefixSum[i]表示nums[0..i-1]的和（长度为n+1，prefixSum[0] = 0便于处理空区间）。于是：

• 索引i的左侧和 =prefixSum[i]；
• 索引i的右侧和 =prefixSum[n] - prefixSum[i+1]（即总和减去包含nums[i]在内的前缀部分）。

右侧和公式中显式减去了prefixSum[i+1]，从而把枢轴元素nums[i]本身排除在两侧区间之外。

算法步骤

1. 构建前缀和数组：prefixSum[i+1] = prefixSum[i] + nums[i]；
2. 遍历每个索引i：
   • 左侧和 =prefixSum[i]；
   • 右侧和 =prefixSum[n] - prefixSum[i+1]；
   • 若两者相等，返回i；
3. 遍历结束未找到，返回-1。

多语言实现

class Solution: def pivotIndex(self, nums: List[int]) -> int: n = len(nums) prefixSum = [0] * (n + 1) for i in range(n): prefixSum[i + 1] = prefixSum[i] + nums[i] for i in range(n): leftSum = prefixSum[i] rightSum = prefixSum[n] - prefixSum[i + 1] if leftSum == rightSum: return i return -1

public class Solution { public int pivotIndex(int[] nums) { int n = nums.length; int[] prefixSum = new int[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } for (int i = 0; i < n; i++) { int leftSum = prefixSum[i]; int rightSum = prefixSum[n] - prefixSum[i + 1]; if (leftSum == rightSum) { return i; } } return -1; } }

class Solution { public: int pivotIndex(vector<int>& nums) { int n = nums.size(); vector<int> prefixSum(n + 1, 0); for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } for (int i = 0; i < n; i++) { int leftSum = prefixSum[i]; int rightSum = prefixSum[n] - prefixSum[i + 1]; if (leftSum == rightSum) { return i; } } return -1; } };

class Solution { /** * @param {number[]} nums * @return {number} */ pivotIndex(nums) { const n = nums.length; const prefixSum = new Array(n + 1).fill(0); for (let i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } for (let i = 0; i < n; i++) { const leftSum = prefixSum[i]; const rightSum = prefixSum[n] - prefixSum[i + 1]; if (leftSum === rightSum) { return i; } } return -1; } }

public class Solution { public int PivotIndex(int[] nums) { int n = nums.Length; int[] prefixSum = new int[n + 1]; for (int i = 0; i < n; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } for (int i = 0; i < n; i++) { int leftSum = prefixSum[i]; int rightSum = prefixSum[n] - prefixSum[i + 1]; if (leftSum == rightSum) { return i; } } return -1; } }

func pivotIndex(nums []int) int { n := len(nums) prefixSum := make([]int, n+1) for i := 0; i < n; i++ { prefixSum[i+1] = prefixSum[i] + nums[i] } for i := 0; i < n; i++ { leftSum := prefixSum[i] rightSum := prefixSum[n] - prefixSum[i+1] if leftSum == rightSum { return i } } return -1 }

class Solution { fun pivotIndex(nums: IntArray): Int { val n = nums.size val prefixSum = IntArray(n + 1) for (i in 0 until n) { prefixSum[i + 1] = prefixSum[i] + nums[i] } for (i in 0 until n) { val leftSum = prefixSum[i] val rightSum = prefixSum[n] - prefixSum[i + 1] if (leftSum == rightSum) { return i } } return -1 } }

class Solution { func pivotIndex(_ nums: [Int]) -> Int { let n = nums.count var prefixSum = Int for i in 0..<n { prefixSum[i + 1] = prefixSum[i] + nums[i] } for i in 0..<n { let leftSum = prefixSum[i] let rightSum = prefixSum[n] - prefixSum[i + 1] if leftSum == rightSum { return i } } return -1 } }

impl Solution { pub fn pivot_index(nums: Vec<i32>) -> i32 { let n = nums.len(); let mut prefix_sum = vec![0; n + 1]; for i in 0..n { prefix_sum[i + 1] = prefix_sum[i] + nums[i]; } for i in 0..n { let left_sum = prefix_sum[i]; let right_sum = prefix_sum[n] - prefix_sum[i + 1]; if left_sum == right_sum { return i as i32; } } -1 } }

复杂度分析

• 时间复杂度：$O(n)$。一次构建前缀和 + 一次线性扫描。
• 空间复杂度：$O(n)$。需要长度为n+1的前缀和数组。

解法三：前缀和滚动优化（最优解）

思路

解法二的 O(n) 空间可以进一步压缩为 O(1)。核心洞察是：右侧和 = 总和 - 左侧和 - 当前元素。这样我们只需要维护一个随遍历递增的leftSum变量，不再需要前缀和数组。

推导过程：设total为数组总和。当扫描到索引i时，leftSum恰好是nums[0..i-1]的和，而右侧和必然等于total - leftSum - nums[i]（从总和里去掉左侧部分和枢轴元素本身）。比较之后，再把nums[i]累加进leftSum，进入下一个索引。

算法步骤

1. 计算数组总和total；
2. 初始化leftSum = 0；
3. 遍历每个索引i：
   • 计算rightSum = total - leftSum - nums[i]；
   • 若leftSum == rightSum，返回i；
   • 将nums[i]累加到leftSum；
4. 遍历结束未找到，返回-1。

多语言实现

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

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

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++) { int rightSum = total - leftSum - nums[i]; if (leftSum == rightSum) { return i; } leftSum += nums[i]; } return -1; } };

class Solution { /** * @param {number[]} nums * @return {number} */ pivotIndex(nums) { let total = 0; for (let num of nums) { total += num; } let leftSum = 0; for (let i = 0; i < nums.length; i++) { let rightSum = total - leftSum - nums[i]; if (leftSum === rightSum) { return i; } leftSum += nums[i]; } return -1; } }

public class Solution { public int PivotIndex(int[] nums) { int total = 0; foreach (int num in nums) { total += num; } int leftSum = 0; for (int i = 0; i < nums.Length; i++) { int rightSum = total - nums[i] - leftSum; if (leftSum == rightSum) { return i; } leftSum += nums[i]; } return -1; } }

func pivotIndex(nums []int) int { total := 0 for _, num := range nums { total += num } leftSum := 0 for i := 0; i < len(nums); i++ { rightSum := total - leftSum - nums[i] if leftSum == rightSum { return i } leftSum += nums[i] } return -1 }

class Solution { fun pivotIndex(nums: IntArray): Int { var total = 0 for (num in nums) { total += num } var leftSum = 0 for (i in nums.indices) { val rightSum = total - leftSum - nums[i] if (leftSum == rightSum) { return i } leftSum += nums[i] } return -1 } }

class Solution { func pivotIndex(_ nums: [Int]) -> Int { var total = 0 for num in nums { total += num } var leftSum = 0 for i in 0..<nums.count { let rightSum = total - leftSum - nums[i] if leftSum == rightSum { return i } leftSum += nums[i] } return -1 } }

impl Solution { pub fn pivot_index(nums: Vec<i32>) -> i32 { let total: i32 = nums.iter().sum(); let mut left_sum = 0; for i in 0..nums.len() { let right_sum = total - left_sum - nums[i]; if left_sum == right_sum { return i as i32; } left_sum += nums[i]; } -1 } }

复杂度分析

• 时间复杂度：$O(n)$。求总和一次遍历，判断枢轴再一次遍历。
• 空间复杂度：$O(1)$。仅使用total与leftSum两个变量，与输入规模无关。

三种解法对比

三个解法的演进脉络非常清晰：暴力 → 空间换时间（前缀和数组）→ 数学恒等式消去额外空间。这正好对应了前缀和类问题从入门到最优解的典型优化路径。

常见陷阱（Common Pitfalls）

陷阱一：把空区间和误当作"不存在"

当枢轴在索引0时，左侧是空区间，其和为0；当枢轴在最后一个索引时，右侧空区间的和同样为0。题目明确将空区间和定义为0，因此首尾索引都是合法的枢轴候选，不能想当然地跳过。

例如nums = [2,1,-1]的答案是0，因为nums[0]左侧为空（和为0），右侧1 + (-1) = 0。若在代码中从i = 1开始遍历，就会漏掉这个正确答案。

陷阱二：把枢轴元素本身算进某一侧的和

枢轴索引nums[i]本身既不属于左侧和，也不属于右侧和。常见的错误有两种：

• 把左侧和累加到包含nums[i]（例如leftSum更新时机放在比较之前）；
• 把右侧和的起点设为i而不是i + 1。

正确写法是显式排除枢轴元素：rightSum = total - leftSum - nums[i]。对照三种解法的公式：

• 解法二：rightSum = prefixSum[n] - prefixSum[i + 1]（prefixSum[i+1]已包含nums[i]，相减后被排除）；
• 解法三：rightSum = total - leftSum - nums[i]（总和去掉左侧部分和枢轴元素本身）。

两种公式在数学上是等价的，都保证了枢轴元素不出现在任何一侧。

仓库源码对照验证

本仓库为该题提供了多种语言的提交级实现（文件命名统一为0724-find-pivot-index.*），绝大多数采用解法三的最优形式，可直接对照上文代码：

• python/0724-find-pivot-index.py：先total = sum(nums)求总和，再单次遍历比较leftSum与rightSum；
• java/0724-find-pivot-index.java：与上文解法三 Java 版一致；
• javascript/0724-find-pivot-index.js：使用reduce求总和，再用 while 循环推进leftSum；
• cpp/0724-find-pivot-index.cpp：先累加total，循环中动态更新rightSum；
• csharp/0724-find-pivot-index.cs：利用 LINQnums.Sum()求总和；
• go/0724-find-pivot-index.go：range求总和 + 单次扫描；
• kotlin/0724-find-pivot-index.kt：先累加rightSum到总和，再扫描比对；
• rust/0724-find-pivot-index.rs：用nums.iter().sum()与enumerate()完成实现；
• c/0724-find-pivot-index.c：一个值得注意的变体——先让right_sum等于总和，然后随遍历先right_sum -= nums[i]再比较，等效于total - left_sum - nums[i]的递推写法；
• swift/0724-find-pivot-index.swift：采用了解法二（前缀和数组）的实现，通过原地累加构造前缀和并分情况取left/right，可作为对照理解两种思路的差异；
• typescript/0724-find-pivot-index.ts：TypeScript 版本同样可运行。

这些实现与本文三种解法一一对应，验证了原文档的算法描述与实际提交代码的一致性；README 的完成度表中同样收录了该题（见 README.md）。

扩展与延伸

掌握本题后，可以进一步理解以下关联问题，体会前缀和思想的复用：

• Range Sum Query - Immutable（303）：把前缀和数组封装成类，支持任意sumRange(i, j)的 O(1) 查询，对应本仓库 articles/range-sum-query-immutable.md；
• Split Array Largest Sum / Partition Equal Subset Sum：在前缀和（或子数组和）基础上叠加二分、DP 等技巧；
• Find the Pivot Integer（2485）：同为"左右两侧和相等"的变体题，仓库 javascript/2485-find-the-pivot-integer.js 有对应实现。

总结

LeetCode 724 Find Pivot Index 是检验前缀和思想的经典入门题。本文从暴力枚举（$O(n^2)$）出发，先后给出前缀和数组（$O(n)$ 时间 / $O(n)$ 空间）与滚动前缀和（$O(n)$ 时间 / $O(1)$ 空间）两种递进优化，并完整覆盖了首尾边界与枢轴元素排除两大易错点。面试与实战中，推荐直接写出解法三：一次求总和、一次扫描、两个变量，代码简短且不易出错，这也是本仓库绝大多数语言提交采用的方案。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode