LeetCode 724. 寻找数组的中心下标：前缀和双变量遍历解法（Python / Java / C++）

LeetCode 724. 寻找数组的中心下标前缀和双变量遍历解法Python / Java / C【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本篇指南围绕《Krahets 笔面试精选 88 题》题单中的经典数组题「寻找数组的中心下标」LeetCode 724展开讲解如何在不借助前缀和数组的前提下仅用两个累计变量在单次遍历中定位中心下标。读完本文你将掌握该题的推导思路、三种语言Python / Java / C的完整可运行实现、int 数据范围的安全性论证以及本仓库中对应的源码与测试用例组织方式可直接在本地编译运行验证。题目回顾什么是「中心下标」给定一个整数数组nums请计算数组的中心下标。中心下标是一个数组下标其左侧所有元素相加的和等于右侧所有元素相加的和。如果数组不存在中心下标返回-1如果存在多个中心下标则返回最左边的那一个。需要注意中心下标两侧的计算都不包含中心下标本身位置的元素左侧元素和 右侧元素和 均不包含下标 i 处的 nums[i]典型示例nums [1, 7, 3, 6, 5, 6]下标3是中心下标因为左侧1 7 3 11右侧5 6 11两侧相等。这个用例也正是本仓库 C 源码中的测试用例见 lc_724_find_pivot_index_s1.cpp。解题思路两个累计变量 单次遍历原文档724. 寻找数组的中心下标.md指出题目仅说明是整数数组无其他已知条件因此考虑直接遍历数组而不引入额外数据结构。设索引 $i$ 对应变量「左侧元素相加和sum_left」和「右侧元素相加和sum_right」算法流程如下遍历数组nums每轮先更新sum_right再比较、后更新sum_left遍历中遇到满足sum_left sum_right时说明当前索引即为中心下标直接返回若遍历完成仍未找到返回-1。初始化技巧等价于「哨兵下标 -1」一个关键的设计是初始化方式。原文档给出巧妙的等价理解初始化时相当于索引 $i -1$此时sum_left 0sum_right 所有元素的和。也就是说在进入循环之前sum_left 0下标-1左侧没有任何元素和为0sum_right sum(nums)下标-1右侧包含整个数组和为所有元素之和。每次迭代中由于指针前进到下标i元素nums[i]从「右侧」划归到「中心位置」因此先执行sum_right - nums[i]随后比较两侧若相等则返回i否则把nums[i]累加进左侧再执行sum_left nums[i]进入下一轮。这个「先减右侧、后加左侧」的顺序保证了任意下标 $i$ 上sum_left与sum_right恰好分别代表 $[0, i-1]$ 与 $[i1, n-1]$ 区间的元素和。遍历全过程推演以nums [1, 7, 3, 6, 5, 6]为例总和无须单独存储此处用于推演下标 isum_left比较前sum_right更新后是否相等返回0027否-1120否-2817否-31111是3第 3 轮命中sum_left sum_right返回3与仓库 C 用例的期望输出一致。边界情况为什么 int 类型足够安全原文档在「代码」一节特别提醒需要考虑大数越界问题。题目对输入给出明确取值范围$$ 1 \leq nums.length \leq 10^4 \ -1000 \leq nums[i] \leq 1000 $$由绝对值不等式可推出「元素相加和」的取值范围为 $[-10^7, 10^7]$最大和$10^4 \times 1000 10^7$最小和$10^4 \times (-1000) -10^7$该区间完全落在 32 位int约 $\pm 2.1 \times 10^9$的表示范围内因此sum_left、sum_right在 Python、Java、C 三种语言中使用int类型即可无需使用long或大数运算。这也是该题可以直接对「和」做相等判断而不必担心溢出的前提代码可读性也因此大幅提升。代码实现三种语言对照以下代码与本仓库源码保持完全一致均已内置驱动代码与测试用例可直接运行。Pythonclass Solution: def pivotIndex(self, nums: List[int]) - int: sum_left, sum_right 0, sum(nums) for i in range(len(nums)): sum_right - nums[i] # 若左侧元素和等于右侧元素和返回中心下标 i if sum_left sum_right: return i sum_left nums[i] return -1对应仓库文件lc_724_find_pivot_index.py其测试用例为[1, 2, 3, 4, 5]该数组不存在中心下标程序输出-1。Javaclass Solution { public int pivotIndex(int[] nums) { int sumLeft 0, sumRight Arrays.stream(nums).sum(); for (int i 0; i nums.length; i) { sumRight - nums[i]; // 若左侧元素和等于右侧元素和返回中心下标 i if (sumLeft sumRight) return i; sumLeft nums[i]; } return -1; } }对应仓库文件lc_724_find_pivot_index.java。Java 侧同样使用[1, 2, 3, 4, 5]作为测试用例期望输出-1求和借助Arrays.stream(nums).sum()完成该表达式返回int类型与前文的数据范围论证吻合。Cclass Solution { public: int pivotIndex(vectorint nums) { int sumLeft 0, sumRight accumulate(nums.begin(), nums.end(), 0); for (int i 0; i nums.size(); i) { sumRight - nums[i]; // 若左侧元素和等于右侧元素和返回中心下标 i if (sumLeft sumRight) return i; sumLeft nums[i]; } return -1; } };对应仓库文件lc_724_find_pivot_index_s1.cpp其测试用例为{1, 7, 3, 6, 5, 6}期望输出3。求和使用标准库算法accumulate(nums.begin(), nums.end(), 0)其中初始值0为int符合取值范围约束。复杂度分析时间复杂度 $O(N)$其中 $N$ 为数组nums长度。求和操作使用 $O(N)$ 线性时间遍历nums最差使用 $O(N)$ 线性时间。总时间仍为线性阶。空间复杂度 $O(1)$变量sum_left、sum_right使用常数大小空间未引入任何与 $N$ 相关的辅助数据结构。该解法的优势在于它没有使用额外的前缀和数组如pre[i] pre[i-1] nums[i]而是借助「总和固定」这一不变式用两个变量动态维护左右两侧之和将空间开销压到常数级是典型的「原地单趟扫描」写法。仓库中的组织方式与运行验证本仓库将题解文档与可运行代码分离存放题解文档selected_coding_interview/docs/724. 寻找数组的中心下标.md属于《Krahets 笔面试精选 88 题》题单README 中说明该项目包含「图解算法数据结构」「Krahets 笔面试精选 88 题」「剑指 Offer」三部分题解见 README.mdPython 源码lc_724_find_pivot_index.py通过from include import *引入仓库公共工具模块见 include 目录Java 源码lc_724_find_pivot_index.java依赖include.*公共包C 源码lc_724_find_pivot_index_s1.cpp通过#include ../include/include.hpp引入公共头文件。三种语言的源码均以// Solution Code 与// Driver Code 明确划分解法与测试入口内置main直接打印结果读者只需进入对应目录编译运行即可复现输出Python 输出-1C 输出3。小结「寻找数组的中心下标」是一道非常适合面试热身的数组遍历题它考察的核心能力包括不变式思维认识到「左侧和 中心元素 右侧和 总和」从而用两个变量完成两侧的动态维护边界处理理解中心下标两侧均不含自身且初始状态等价于哨兵下标-1数值安全能根据题目数据范围论证int类型不会溢出复杂度意识在 $O(N)$ 时间内以 $O(1)$ 空间解决问题。掌握这种「双变量单趟扫描」的写法后还可将其迁移到「两侧和比较」「平衡点查找」等一类问题中是前缀和思想的入门级铺垫。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考