LeetCode Hot 100 · 普通数组篇

普通数组是手撕面试里出场率最高的一类题：题干短、约束硬、套路清晰，考官要看的不是「你会不会写循环」，而是你在 O(n)/O(1) 的极限约束下，能不能想到把数组本身当容器来用。本篇五题各有一个标志性技巧——Kadane 贪心 DP、排序后贪心、三次翻转、前缀积 × 后缀积、原地哈希，几乎覆盖了数组题全部的高频套路。

#53 最大子数组和

题意

给你一个整数数组 nums，找出具有最大和的连续子数组（至少包含一个元素），返回其最大和。

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6

难点与易错点

1. 全负数数组：如果答案初始化为 0，全负数数组会错误返回 0（而正确答案是最大的那个负数）。所以 ans 必须初始化为 nums[0]（或 Integer.MIN_VALUE）。
2. 「断开」的时机：只有当「前面累加的前缀和本身已经是负值」时才断开；不是一遇到负数就断开。单个负数元素本身仍可能比「负前缀 + 负数」更大。
3. 至少包含一个元素：不能返回空子数组的 0，这与「子序列」类题不同，边界要读清。

题目本质：贪心 DP（Kadane 算法）——连续前缀若已为负，则对后续子数组是拖累，应抛弃并从当前元素重新开始。

现实类比：股票累计收益。如果之前的累计收益已经是负的，不如从今天重新开始计算，同时记录历史最高单段收益。

解法一：暴力 / 直观

枚举所有子数组（起点 i + 终点 j），累加求和取最大。

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int ans = nums[0]; // 至少包含一个元素，初始化为首元素防全负

        for (int i = 0; i < n; i++) {       // 子数组起点
            int sum = 0;
            for (int j = i; j < n; j++) {   // 子数组终点，边扩展边累加
                sum += nums[j];
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }
}

复杂度逐步推导：外层 i 有 n 种取值；对每个 i，内层 j 从 i 走到 n-1，执行约 n - i 次。总次数为 n + (n-1) + ... + 1 = n(n+1)/2，所以时间复杂度 O(n²)；只用两个标量变量，空间 O(1)。

瓶颈：每一对 (i, j) 都重新求和，sum(i,j) 与 sum(i,j-1) 之间只差一个 nums[j]，暴力没有复用这个递推关系，做了大量重复加法。

解法二：优化 / 最优（Kadane）

维护 pre = 以当前元素结尾的最大子数组和。递推关系：pre = max(num, pre + num)——若前面的前缀和为负，则断开，从 num 重新开始；否则继续累加。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;          // 以当前元素结尾的最大子数组和
        int ans = nums[0];    // 全局最大值，初始为第一个元素（防止全负情况）

        for (int num : nums) {
            // 若 pre 为负，则加上它只会让结果更小
            // 不如从 num 重新开始（舍弃前面的负贡献）
            pre = Math.max(num, pre + num);
            ans = Math.max(ans, pre);
        }
        return ans;
    }
}

> **💭 思考**：为什么这题能从 O(n²) 优化到 O(n)，核心状态 `pre` 是怎么想出来的？一步步想——暴力枚举所有 `(i, j)` 的瓶颈是「`sum(i,j)` 和 `sum(i,j-1)` 只差一个元素，却要重算」。想复用，就把「以当前位置结尾的最大子数组和」定义成状态 `pre`，于是 `pre` 可以由 `pre + num` 递推，不用重扫。关键在「断开时机」：前缀和一旦为负，继续加只会拖累后面的元素，所以 `pre = max(num, pre + num)`——注意是「负前缀」才断，不是「遇到负数」就断，单个负数可能正是新子数组的起点。这一句既是状态定义，也是贪心正确性的全部。

复杂度逐步推导：循环体内只有一次 Math.max 比较和一次加法，每个元素访问且仅访问一次；循环一共执行 n 次，每次 O(1)，所以时间复杂度 O(n)。空间上，全程只维护 pre 与 ans 两个整型变量，与输入规模无关，因此空间复杂度 O(1)。

多解法对比

本题约束是 n 可达 10⁵，O(n²) 会超时（10¹⁰ 量级运算）。Kadane 单次扫描、常数空间，且代码极短，是面试标准答案——考官真正考的是「前缀和为负就断开」这个贪心正确性。

CodeTop 变体

• 字节/腾讯高频追问：不只返回最大和，还要返回最大子数组的起止下标 [start, end]（在 pre 断开处记录新的起点，ans 更新时同步记录终点）。
• 同套路延伸：
  • 918. 环形子数组的最大和——数组首尾相连，思路 = max(最大子段和, 总和 - 最小子段和)，注意全负特判。
  • 152. 乘积最大子数组——把「加」换成「乘」，需同时维护最大、最小两个状态（负数会让最小变最大）。

#56 合并区间

题意

以数组 intervals 表示若干区间 [start, end]，合并所有重叠的区间，返回不重叠的区间数组（结果覆盖所有输入区间）。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

难点与易错点

1. 重叠判断的边界：两区间重叠当且仅当 cur[0] <= last[1]（排序后）；写错成 < 会漏掉「端点恰好相接」的情况（本题要求合并，相接也算重叠）。
2. 合并右端点必须取 max：[1,5] 和 [2,4] 合并结果是 [1,5]，不是 [1,4]——必须 last[1] = Math.max(last[1], cur[1])，不能简单赋值 cur[1]，因为当前区间可能被上一个区间完全包含。
3. 必须排序：不按左端点排序就无法保证「当前区间只可能和结果末尾区间重叠」，贪心会失效。

题目本质：排序后贪心合并——按左端点排序后，当前区间与上一个区间有重叠（cur[0] <= last[1]）就合并（右端点取两者最大），否则直接加入结果。

现实类比：合并会议时间段。把所有会议按开始时间排序，逐个检查是否和前一个会议重叠，重叠就合并延长，否则前一个会议已结束，开始下一场。

解法一：暴力 / 直观

不排序，反复两两扫描：发现任意两个重叠区间就合并成一个，直到某一轮没有任何合并发生。

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();
        for (int[] it : intervals) {
            list.add(new int[]{it[0], it[1]});
        }

        boolean changed = true;
        while (changed) {              // 每轮至少合并一对，直到稳定
            changed = false;
            outer:
            for (int i = 0; i < list.size(); i++) {
                for (int j = i + 1; j < list.size(); j++) {
                    int[] a = list.get(i);
                    int[] b = list.get(j);
                    // 两区间重叠判断：a.start <= b.end && b.start <= a.end
                    if (a[0] <= b[1] && b[0] <= a[1]) {
                        a[0] = Math.min(a[0], b[0]);
                        a[1] = Math.max(a[1], b[1]);
                        list.remove(j);       // 被合并的区间删掉
                        changed = true;
                        break outer;          // 本轮先合并一对，下一轮继续
                    }
                }
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

复杂度逐步推导：最坏情况下每次 while 循环只合并掉一个区间，区间个数从 n 逐步减到 1，共约 n 轮；每轮内部双重循环扫描剩余区间，约 O(n²)。因此最坏时间复杂度为 O(n³)（平均也更差于 O(n²)）；除结果列表外无额外空间，空间 O(n)（结果本身）。

瓶颈：没有排序就无法用「和末尾区间比较」这个 O(1) 判断代替「和所有区间两两比较」，导致大量重复扫描。

解法二：优化 / 最优（排序 + 贪心）

先按左端点升序排序，之后每个区间只需和结果列表末尾的区间比较一次。

class Solution {
    public int[][] merge(int[][] intervals) {
        // 按每个区间的左端点升序排序，Java 8 lambda
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>();

        for (int[] interval : intervals) {
            int size = merged.size();
            // 无区间，或当前区间与末尾区间不重叠：直接加入
            if (size == 0 || merged.get(size - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                // 重叠：合并，右端点取两者较大值（注意不是简单赋值）
                merged.get(size - 1)[1] = Math.max(merged.get(size - 1)[1], interval[1]);
            }
        }

        // List<int[]> 转回 int[][] 数组
        return merged.toArray(new int[merged.size()][]);
    }
}

> **💭 思考**：为什么合并区间一定要「先排序」？一步步想——暴力两两合并的瓶颈是「没有排序，就只能和所有区间两两比较」，最坏 O(n³)。一旦想到「只要排个序，当前区间就只会和结果末尾那个区间重叠」，重叠判断就从「和所有人比」降成「和最后一个比」的 O(1)——这正是排序后贪心的由来。所以看到「区间」类题目，第一反应先按端点排序，几乎总能换来一个贪心结构。

复杂度逐步推导：排序使用 Arrays.sort（对对象数组是 TimSort / 归并排序），比较次数为 O(n log n)；排序之后是单次线性扫描，每个区间只看一次，O(n)。两者相加，总时间复杂度由排序主导，为 O(n log n)。空间上，merged 列表最多存 n 个区间，因此空间复杂度 O(n)（排序 TimSort 还有 O(n) 临时空间）。

多解法对比

在 n 可达 10⁴ 的约束下，暴力 O(n³) 完全不可用；排序 O(n log n) 是「区间类」题目的通用下限（只要涉及区间端点顺序，几乎都要先排序）。面试真正区分度在于：右端点取 max、toArray 的正确用法、以及重叠边界的 < vs <=。

CodeTop 变体

• 字节/腾讯真实追问：在合并后的区间里，判断一个新区间是否被完全覆盖（等价于「插入后区间数量是否变化」）。
• 同套路延伸（区间贪心是笔试重灾区）：
  • 57. 插入区间——已排序 + 一个新区间，二分/线性定位后一次插入合并。
  • 252/253. 会议室 I/II——判断能否全程不冲突 / 最少需要几间会议室（差分或最小堆）。
  • 435. 无重叠区间 / 452. 用最少数量的箭引爆气球——「最多不重叠区间数」的贪心双胞胎，按右端点排序。

#189 轮转数组

题意

给定整数数组 nums，将数组元素向右轮转 k 个位置（原地修改，k 非负）。

输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]

难点与易错点

1. k 可能大于 n：必须先 k %= n。k = n 时轮转结果等于原数组；不取模会导致 reverse(nums, 0, k-1) 越界。
2. 要求原地、O(1) 空间：直接开新数组是 O(n) 空间，不满足进阶要求（面试通常要求 O(1)）。
3. 边界 k = 0 或 n = 1：取模后 k = 0，三次翻转应自然空转（reverse(0, -1) 等需保证区间合法，i < j 不成立直接返回），代码要经得起这类退化输入。

题目本质：三次翻转法——先整体翻转，再翻转前 k 个，再翻转后 n-k 个，结果就是向右轮转 k 位；数学上等价于「分段逆序后全逆序」。

现实类比：排队换位。全队先整体反向站，再把前 k 人内部反向、后 n-k 人内部反向，最终效果等于最后 k 人移到队首。

解法一：暴力 / 直观（辅助数组）

新开一个数组，把每个元素直接放到它轮转后的目标位置 (i + k) % n。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;                       // 防止 k >= n

        int[] tmp = new int[n];
        for (int i = 0; i < n; i++) {
            tmp[(i + k) % n] = nums[i]; // 直接放到轮转后的目标下标
        }
        // 把临时数组拷贝回原数组
        System.arraycopy(tmp, 0, nums, 0, n);
    }
}

复杂度逐步推导：一次线性遍历 + 一次 arraycopy，各 O(n)，总时间复杂度 O(n)；额外开了一个长度 n 的数组，空间复杂度 O(n)。

瓶颈：空间 O(n) 不满足「原地 O(1)」的进阶要求，在要求原地修改时不可用。

解法二：优化 / 最优（三次翻转）

原地操作，零额外数组。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n; // 防止 k >= n 的情况（等价于轮转 k%n 次）

        // 三次翻转法：
        // 先整体翻转，再翻前 k，再翻后 n-k
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    // 原地翻转 nums[i..j]
    private void reverse(int[] nums, int i, int j) {
        while (i < j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
}

复杂度逐步推导：三次 reverse 分别处理区间 [0, n-1]、[0, k-1]、[k, n-1]，三段区间长度之和恰为 n（n + k + (n-k) = 2n，但交换发生在原地，实际元素交换总次数约 n 次）；每次交换 O(1)，故总时间复杂度 O(n)。空间上，只用一个临时变量 tmp 完成交换，没有分配任何与 n 相关的空间，因此空间复杂度 O(1)。

补充：另有一种「环状替换」也能做到 O(n)/O(1)（按 gcd(n, k) 个环逐环替换），但实现易错；三次翻转是更稳、更好解释的面试答案。

多解法对比

本题要求「原地」时，辅助数组直接被否；三次翻转三步对称、好记好验证（左右翻转的区间边界清晰），且 O(1) 空间，是面试最优解。

CodeTop 变体

• 字节真实追问：把「向右轮转」改成向左轮转 k 位（只需把三段翻转顺序对调：先翻前 n-k，再翻后 k，最后整体翻）。
• 同套路延伸：
  • 61. 旋转链表——链表的轮转，先闭合成环再在 n - k % n 处断开。
  • 剑指 Offer 58-II. 左旋转字符串——字符串轮转，同三次翻转思路。
  • 283. 移动零——「把 0 移到末尾」可看作一种受限的原地重排，双指针同套路。

#238 除自身以外数组的乘积

题意

给你整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。不能使用除法，要求 O(n) 时间。

输入：nums = [1,2,3,4]
输出：[24,12,8,6]

难点与易错点

1. 禁止除法：如果数组里有 0，用「总乘积 ÷ nums[i]」会除零；题目明确禁用除法，必须用乘法拆解。
2. 「除自身」≠ 包含自身：answer[i] 只乘左右两边，千万别把 nums[i] 自己乘进去（循环里先乘 pre 再更新 pre *= nums[i] 的顺序很关键）。
3. O(1) 额外空间：进阶要求不计结果数组外只用常数空间，不能用两个完整的前缀/后缀数组。

题目本质：前缀积 × 后缀积——answer[i] = 左边所有元素的乘积 × 右边所有元素的乘积，分两次遍历分别累积前缀积和后缀积，原地合并。

现实类比：工厂流水线质检。每件产品的「质量指标」等于它左边所有零件的合格率乘以右边所有零件的合格率，先从左到右记录前缀，再从右到左扫一遍乘上后缀。

解法一：暴力 / 直观（左右两个数组）

分别构建 left[i]（i 左边所有元素的乘积）和 right[i]（i 右边所有元素的乘积），再相乘。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;

        // left[i] = nums[0] * ... * nums[i-1]
        int[] left = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        // right[i] = nums[i+1] * ... * nums[n-1]
        int[] right = new int[n];
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = left[i] * right[i]; // 左 × 右
        }
        return ans;
    }
}

复杂度逐步推导：三次线性遍历（构造 left、构造 right、合并），每次 O(n)，总时间复杂度 O(n)；额外分配了 left、right 两个长度 n 的数组，空间复杂度 O(n)（不含结果数组）。

瓶颈：空间 O(n)，不满足进阶 O(1) 要求——left 数组其实可以复用结果数组或用一个滚动变量替代。

解法二：优化 / 最优（单数组 + 滚动前缀积）

用一个结果数组先存后缀积，再用滚动变量 pre 从左边把前缀积乘进去，原地合并。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // 先用 suf 数组存储后缀积，最后原地改写为答案
        int[] suf = new int[n];

        // 构建后缀积：suf[i] = nums[i+1] * ... * nums[n-1]
        suf[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suf[i] = suf[i + 1] * nums[i + 1];
        }

        // 从左到右，滚动计算前缀积并与后缀积合并
        int pre = 1; // pre 代表 nums[0] * ... * nums[i-1]
        for (int i = 0; i < n; i++) {
            suf[i] *= pre;  // answer[i] = 前缀积 * 后缀积
            pre *= nums[i]; // 更新前缀积，为下一个 i 做准备
        }

        return suf;
    }
}

> **💭 思考**：这题「禁止除法」后，`answer[i]` 该怎么不重复算乘法？一步步想——先想到最直白的「左右两个数组」：`answer[i] = left[i] × right[i]`，左边乘积和右边乘积各扫一遍。再想空间优化：`right`（或 `left`）这个中间数组其实可以复用「输出数组本身」先存一边，而另一边只要一个滚动变量 `pre` 边扫边乘进去——于是第二个数组被一个变量取代，额外空间从 O(n) 压到 O(1)。「用输出数组当中间容器」是原地优化题的经典套路。

复杂度逐步推导：第一步从右往左构建后缀积，循环 n 次；第二步从左往右合并，循环 n 次；两次遍历互不嵌套，每次循环体 O(1)，总时间复杂度 O(n)。空间上，只有一个结果数组 suf（题目允许不计入额外空间），额外只用了 pre 一个变量，因此额外空间复杂度 O(1)。

多解法对比

这题面试时的标准叙事是：先讲「左右两个数组」让思路落地，再指出 left 数组可以用滚动变量 pre 替代、复用后缀数组，把空间从 O(n) 压到 O(1)。核心考察点是用输出数组本身作为中间状态容器，这是「原地优化」的经典手法。

CodeTop 变体

• 字节高频追问：如果题目允许除法但数组里可能有 0，怎么写？（先统计 0 的个数与位置，0 多于一个则全为 0，恰一个 0 时只有该位置为非零乘积。）
• 同套路延伸：
  • 152. 乘积最大子数组——前缀/后缀乘积的动态规划版，同时维护正负两个状态。
  • 前缀和系列（如 560. 和为 K 的子数组、238 本质是前缀和思想的「乘」版本）——用哈希表 + 前缀统计。

#41 缺失的第一个正数

题意

给你一个未排序的整数数组 nums，找出其中没有出现的最小正整数。要求 O(n) 时间、O(1) 额外空间。

输入：nums = [1,2,0]
输出：3

难点与易错点

1. O(1) 空间是最大门槛：直观的哈希表或排序都违反约束，必须把数组本身当哈希表用（原地哈希）。
2. 循环交换防死循环：只有当 nums[nums[i]-1] != nums[i] 时才交换；若目标位置已经是正确值（重复元素），再交换会无限循环。
3. 忽略越界值：负数、0、大于 n 的数都不可能在 [1, n] 里「归位」，直接跳过即可——答案必然在 [1, n+1] 区间内。
4. 交换后不能立刻 i++：交换来的新值可能仍需归位，所以内层用 while 循环，不是 if。

题目本质：原地哈希——把数组本身当作哈希表，将 nums[i] 放到下标 nums[i]-1 的位置；遍历完后找到第一个 nums[i] != i+1 的位置，i+1 就是答案。

现实类比：宿舍号对应。n 个人，每人有一个期望床位（1 到 n）。先让每个人坐到自己期望的位置，最后看哪个床位是空的，那个编号就是最小缺失的床号。

解法一：暴力 / 直观（哈希表）

把所有数放进 HashSet，然后从 1 开始逐个检查是否缺失。

class Solution {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }
        // 答案必然在 [1, n+1] 内，从 1 向上找第一个不存在的正整数
        for (int i = 1; ; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
    }
}

复杂度逐步推导：第一个循环把 n 个元素放入集合，O(n)；第二个循环最多检查到 n+1（因为数组只有 n 个元素，最多占满 1..n），也是 O(n)。总时间复杂度 O(n)；哈希表最多存 n 个元素，空间复杂度 O(n)。

瓶颈：空间 O(n)，违反题目「O(1) 额外空间」的硬约束——面试官会立刻追问「不用额外空间怎么做」。

解法二：优化 / 最优（原地哈希）

把数组本身当作哈希表，让值为 x（且 1 <= x <= n）的元素「坐」到下标 x-1 的位置上。

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 原地哈希：将 nums[i] 放到 nums[nums[i]-1] 的位置
        // 条件：值在 [1,n] 范围内，且目标位置没有正确的值（避免死循环）
        for (int i = 0; i < n; i++) {
            // 循环交换：直到当前元素无法继续归位
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int target = nums[i] - 1; // nums[i] 应当放到的下标
                int tmp = nums[target];
                nums[target] = nums[i];
                nums[i] = tmp;
            }
        }

        // 找第一个不在正确位置的元素
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 数组中 1~n 都存在，最小正整数为 n+1
        return n + 1;
    }
}

> **💭 思考**：O(1) 空间 + 找缺失正数，为什么会想到「把数组本身当哈希表」？一步步想——哈希表 O(n) 空间、排序 O(n log n) 时间，都被「O(n) 时间 + O(1) 空间」卡死。此时盯住值域 `[1, n]`：它恰好能映射到下标 `[0, n-1]`，那么「数组本身」就是一个天然哈希表——让值为 x 的元素坐到下标 `x-1`，最后第一个 `nums[i] != i+1` 的位置就是答案。看到「值域和下标范围一致」这个信号，就该想到原地哈希。而内层用 `while` 不是 `if`，是因为交换来的新值可能还要继续归位。

复杂度逐步推导：外层 for 循环走 n 次，关键是内层 while 循环的总执行次数——每执行一次交换，就有一个元素被放到它的正确位置（nums[i] 归位到 target），而「已归位」的元素不会再被移动，因此交换总次数不超过 n。于是 while 循环整体只执行 O(n) 次，加上最后的检查循环 O(n)，总时间复杂度 O(n)。空间上全程只用一个临时变量 tmp 做交换，没有分配任何辅助容器，空间复杂度 O(1)。

多解法对比

这题是「数组当哈希表」思想的集大成者：数据范围 [1, n] 恰好能映射到下标 [0, n-1]，用下标本身充当桶。时间 O(n) 的证明（每次交换至少归位一个元素）也是面试官最爱追问的点，务必能讲出来。

CodeTop 变体

• 字节/腾讯真实追问：把「缺失的第一个正数」改成「找出数组中所有缺失的正数」（即 448. 找到所有数组中消失的数字，同一个原地哈希框架，最后收集所有 nums[i] != i+1 的下标）。
• 同套路延伸（原地哈希三兄弟，剑指与 Hot 100 高频）：
  • 剑指 Offer 03. 数组中重复的数字——同样是「把 nums[i] 放到 nums[i] 下标」，找到第一个 nums[nums[i]] == nums[i] 的冲突点即为重复数。
  • 442. 数组中重复的数据——出现两次的元素，用下标取负做标记。
  • 287. 寻找重复数——Floyd 判圈（快慢指针），是「下标当边」的另一种映射思想。

本分类小结：五道题串起数组题的三条主线——①「贪心/DP 单次扫描」（53 Kadane）、②「排序后贪心」（56 合并区间）、③「把数组本身当容器做原地变换」（189 三次翻转、238 前缀后缀合并、41 原地哈希）。面试手撕时，先讲清「题目本质 + 现实类比」再落代码，遇到 O(1) 空间的硬约束，第一时间想「数组本身能不能当容器」。

章末提问

1. Kadane 为什么「前缀和为负就断开」，一遇到负数就断开行不行？——结论：不行，只有「累计和已为负」才断开。因为单个负数本身可能比「负前缀 + 负数」更大，遇到负数就断会丢掉以该负数开头、后续转正的子数组。
2. #41 原地哈希为什么是 O(n) 而不是 O(n²)，内层 while 总共交换多少次？——结论：每次交换都让一个元素落到正确位置，而「已归位」的元素不会再被移动，所以交换总次数不超过 n；内层 while 不是每轮都跑满，均摊 O(n)。
3. #238 为什么说「用输出数组当中间容器」是灵魂，空间怎么从 O(n) 压到 O(1)？——结论：因为后缀积本来就要写进结果数组，前缀积可以只用滚动变量 pre 边扫边乘进去、无需第二个数组，于是 left 数组被一个变量取代，额外空间降为 O(1)。