langShift普通数组（题单顺序）
热题 100 - 普通数组分组（按题单顺序）：53 / 56 / 189 / 238 / 41
本页包含题单「普通数组」分组的全部题目，顺序与 list.json 保持一致。
53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1] 输出：1
示例 3：
输入：nums = [5,4,-1,7,8] 输出：23
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
最优解（Kadane：要么接着累加，要么从当前重开）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 问题本质：在连续子数组里挑一段，让它的和最大。
- 朴素想法：枚举所有区间 ((l,r)) 求和取最大，(O(n^2))（或更慢）。
- 关键推理：只看“以 i 结尾”的最优解
设cur表示“以当前位置 i 结尾的最大子数组和”。当我们处理nums[i]=x时，只有两种选择：- 接着前面那段：
cur + x - 从当前重新开一段：
x所以cur = max(x, cur + x)。
- 接着前面那段：
- 为什么这样就够了？：因为任何最优子数组一定有一个“结尾位置”，我们在遍历时把每个结尾的最优都算出来，并用
best取最大即可。 - 直觉解释：如果你手里的
cur已经是负数，那么再加上x只会拖后腿，还不如从x重开。 - 复杂度：时间 (O(n))，空间 (O(1))（只用常数变量）。
类似题目（一维 DP：以 i 结尾的最优）
let cur = initlet best = initfor (const x of arr) {cur = transition(cur, x) // 常见形式：max(x, cur + x)best = Math.max(best, cur)}
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
示例 3：
输入：intervals = [[4,7],[1,4]] 输出：[[1,7]] 解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
最优解（排序 + 一次扫描合并）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 先想清楚为什么要排序：如果区间乱序，你很难判断“当前区间该和谁合并”。把区间按起点排序后，区间会按时间线从左到右出现。
- 排序后的关键性质：当你处理到某个区间
[l,r]，它的起点l一定不小于前面任何区间的起点。 - 用一个“当前正在合并的区间”滚动维护：
- 当前合并段是
[curL, curR]。 - 来了新区间
[l,r]：- 如果
l <= curR：说明有重叠（或刚好相接），两段可以合并，新的右边界是max(curR, r)。 - 如果
l > curR：说明彻底断开，上一段已经不可能再与后面重叠（因为后面起点只会更大），所以把[curL,curR]放进答案，然后开启新段。
- 如果
- 当前合并段是
- 为什么一次扫描就够？：排序保证“不会出现后面区间突然跑到当前区间左边”的情况，所以每个区间只需处理一次。
- 边界情况：输入为空直接返回空；只有一个区间直接返回它本身。
- 复杂度：排序 (O(n\log n)) + 扫描 (O(n))，总时间 (O(n\log n))，空间 (O(1))（不算输出）。
类似题目（区间题通用套路：排序 + 贪心合并/选择）
arr.sort((a, b) => a.start - b.start)let cur = arr[0]for (const x of arr.slice(1)) {if (overlap(cur, x)) cur = merge(cur, x)else {ans.push(cur)cur = x}}ans.push(cur)
189. 轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3 输出:[5,6,7,1,2,3,4]解释: 向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]
示例 2:
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 10 <= k <= 105
进阶：
- 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为
O(1)的 原地 算法解决这个问题吗？
最优解（三次翻转：整体翻转 + 两段翻转）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：把数组整体向右挪
k步，超出末尾的元素绕回开头，要求原地。 - 朴素做法：右移一步做
k次，每次都要挪动很多元素，会很慢。 - 关键观察：右旋 k 等价于把数组分成两段：
- 后
k个元素会跑到最前面 - 前
n-k个元素会整体往后挪
- 后
- 三次翻转的推理（最重要的“魔法”）：
- 假设数组是
A | B（A 长度n-k，B 长度k），目标是B | A。 - 先整体翻转：
reverse(A|B) = reverse(B) | reverse(A) - 再分别把前 k、后 n-k 翻转回来：
reverse(reverse(B)) = Breverse(reverse(A)) = A
- 最终得到
B | A，正好是旋转结果。
- 假设数组是
- 为什么是原地且最优：只做常数次翻转，每次翻转是交换，时间 (O(n))，空间 (O(1))。
- k 的处理细节：一定要先做
k %= n，否则 k 可能很大；k 为 0 时翻转前 k 段会变成空区间，代码需天然兼容（本实现兼容）。
类似题目（翻转技巧：用 reverse 组合实现“切换顺序”）
// 目标：把 A|B 变成 B|A（或其它段交换）reverse(whole)reverse(part1)reverse(part2)
238. 除了自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums =[1,2,3,4]输出:[24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 输入 保证 数组
answer[i]在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
最优解（前缀积 + 后缀积：两趟扫描，O(1) 额外空间）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：对每个位置 i，输出“除了 nums[i] 之外所有数的乘积”，不能用除法。
- 朴素思路：对每个 i 再扫一遍乘起来，(O(n^2))。
- 关键分解：乘积可以拆成左边乘积 × 右边乘积：
ans[i] = (nums[0..i-1] 的乘积) * (nums[i+1..n-1] 的乘积)
- 怎么在 (O(n)) 求出所有左乘积/右乘积？
- 左乘积：从左到右扫一遍，用
left累乘，res[i] = left，再left *= nums[i] - 右乘积：从右到左扫一遍，用
right累乘，res[i] *= right，再right *= nums[i]
- 左乘积：从左到右扫一遍，用
- 为什么不需要额外数组？：
res先存左乘积，再原地乘上右乘积即可，所以额外变量只有left/right两个。 - 0 的情况为什么也能处理？
- 因为我们没有除法，纯粹用乘积拆分；如果某侧有 0，乘出来自然就是 0，符合题意。
- 复杂度：两趟扫描，时间 (O(n))，额外空间 (O(1))（输出数组
res不算额外）。
类似题目（前缀/后缀分解：把全局贡献拆成两边）
// ans[i] = leftAgg(i) * rightAgg(i)let left = identityfor i=0..n-1: ans[i]=left; left=combine(left, nums[i])let right = identityfor i=n-1..0: ans[i]=combine(ans[i], right); right=combine(nums[i], right)
41. 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
O(n) 并且只使用常数级别额外空间的解决方案。
示例 1：
输入：nums = [1,2,0] 输出：3 解释：范围 [1,2] 中的数字都在数组中。
示例 2：
输入：nums = [3,4,-1,1] 输出：2 解释：1 在数组中，但 2 没有。
示例 3：
输入：nums = [7,8,9,11,12] 输出：1 解释：最小的正数 1 没有出现。
提示：
1 <= nums.length <= 105-231 <= nums[i] <= 231 - 1
最优解（原地哈希：把值 x 放到下标 x-1）
正在加载编辑器...
最优解讲解（通俗版 + 推理过程）
- 题意翻译：找数组里缺失的最小正整数。
- 这题的“最优”很苛刻：要 (O(n)) 时间 + (O(1)) 额外空间，所以不能用 Set/排序（排序 (O(n\log n))）。
- 关键观察：答案一定在 ([1, n+1])：
- 如果 1 不在，答案就是 1。
- 如果 1..n 都在，答案就是 n+1。
- 所以我们只关心 1..n 这些值，其它负数/0/大于 n 的数都不影响答案。
- 核心想法：把数组当成“哈希表”用
让值x去它该去的位置：下标x-1。这样如果所有值都摆对了，位置 i 上就应该是i+1。 - 为什么要用 while 反复交换？
- 因为交换后
nums[i]变成了另一个值，它可能也需要被送到自己的位置。 - 反复把当前格子里的值送走，直到这个格子里是“无关值/已就位/重复值”为止。
- 因为交换后
- 如何拿到答案？
- 第二趟从左到右扫，找到第一个
nums[i] != i+1的位置，答案就是i+1。
- 第二趟从左到右扫，找到第一个
- 为什么是 (O(n))？
- 每次交换都把至少一个元素放到了正确位置，元素不会无限交换；整体交换次数是线性的。
- 最常见坑：没处理重复值会造成死循环，所以要用
if (nums[j] === x) break兜住。 - 复杂度：时间 (O(n))，空间 (O(1))。
类似题目（原地哈希模板：值映射到下标）
for (let i = 0; i < n; i++) {while (needSwap(nums[i])) {swap(nums, i, targetIndex(nums[i]))}}// 再扫一遍找第一个不符合的位置