LeetCode Hot 100 · 技巧篇

「技巧」类题目有一个共同特征：它们不依赖复杂的数据结构，而是靠一个巧妙的想法把复杂度压到极致。如果你只会用 HashMap 硬数、只会调 Arrays.sort，那这几道题在面试现场会瞬间暴露短板——因为它们的真正考点，是位运算、摩尔投票、三指针、字典序构造、Floyd 判圈这五类「套路」。

本文 5 道题，每道都给出「暴力 → 最优」的完整推演，复杂度逐步推导，并附上字节 / 腾讯 / 阿里真实的 CodeTop 变体追问。

136. 只出现一次的数字

题意

给定一个非空整数数组，除某个元素只出现一次外，其余每个元素均恰好出现两次，找出那个只出现一次的元素。要求 O(n) 时间、O(1) 空间。

输入：nums = [2,2,1]   输出：1
输入：nums = [4,1,2,1,2]   输出：4

题目本质：这是一道「位运算」题，核心是异或（XOR）的三个性质：a XOR a = 0、0 XOR a = a、以及交换律/结合律。把所有元素异或起来，出现两次的会两两抵消为 0，剩下的就是那个单身元素。

现实类比：找单身宠物。每种宠物都来两只配对，用「配对消除」操作一对一对地抵消，最后手里剩下的那只就是没配上对的。

难点与易错点

1. O(1) 空间的硬约束：直觉上想用 HashMap 计数，时间虽然 O(n) 但空间是 O(n)，直接违反题目要求，面试官会当场问「能不能 O(1) 空间」。
2. 为什么初始值取 0 是对的：因为 0 XOR a = a，所以 res 从 0 出发不会污染结果，这是很多人没想清楚就照抄的点。
3. 负数也能用异或：整数在内存里是补码，异或是「按位」运算，跟符号无关，所以 [-1, 2, -1] 也能正确得到 2，不需要额外处理负数。
4. 顺序无关：异或满足交换律和结合律，a ^ b ^ a = b，所以不需要先排序再配对。

解法一：暴力 / 直观（HashMap 计数）

用哈希表统计每个数字出现次数，再扫一遍找出出现次数为 1 的 key。

import java.util.*;

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        // 第一遍：统计每个数字出现的次数
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        // 第二遍：找出出现次数为 1 的数字
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            if (e.getValue() == 1) {
                return e.getKey();
            }
        }
        return -1; // 按题意不会走到这里
    }
}

复杂度：两遍遍历，时间 O(n)；哈希表最多存 n/2+1 个键，空间 O(n)。

瓶颈：空间 O(n)，不满足题目 O(1) 的要求。这道题的坑就在于「让你想出一个不用额外存储的方案」。

解法二：优化 / 最优（位运算 XOR）

维护单个变量 res，遍历异或所有元素即可。

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;              // 0 ^ a = a，初始 0 不会影响结果
        for (int num : nums) {
            res ^= num;           // 出现两次的数两两抵消为 0
        }
        return res;               // 剩下的就是只出现一次的数
    }
}

> **💭 思考**：看到「每个元素恰好出现两次、只有一个出现一次、要求 O(n) 时间 O(1) 空间」，该往哪想？一步步想——HashMap 计数时间没问题，但空间 O(n) 被 O(1) 硬约束封死；排序后配对空间省了，但时间 O(n log n) 又不满足。两个约束一夹，只剩「原地、常数空间」的位运算方向。而「成对出现、只求唯一」这个信号，恰好对应异或的抵消性质：`a ^ a = 0`、`0 ^ a = a`，再配合交换律/结合律，出现两次的数两两抵消，剩下的就是单身元素——于是 O(1) 空间的解法自然浮现。

复杂度逐步推导：

• 先数循环次数：for 循环恰好执行 n 次，每次循环体只做一次按位异或，这是 CPU 层面的单条指令，常量时间。
• 所以 T(n) = n · O(1) = O(n)，即时间复杂度 O(n)。
• 空间上，只额外声明了 res 一个 int（4 字节）和循环变量，与 n 无关，不随输入规模增长，故空间复杂度 O(1)。

如果面试官认可 Java 8 的流式写法，也可以用一行搞定（本质相同）： return Arrays.stream(nums).reduce(0, (a, b) -> a ^ b);

正确性直觉：设唯一元素为 x，其余元素都成对出现。由交换律/结合律，所有异或可重排成 (a1^a1) ^ (a2^a2) ^ ... ^ x = 0 ^ x = x。

多解法对比

本题约束明确要求 O(n) 时间 + O(1) 空间，只有 XOR 方案能同时满足，因此它是唯一的最优解。

CodeTop 变体

• 137. 只出现一次的数字 II（延伸同套路题）：其余元素出现三次，找只出现一次的那个。异或不再适用，改为「逐位统计」——统计每个二进制位上 1 出现的次数，对 3 取模，余 1 的位拼起来就是答案。真实面试常追问：把「两次」改成「三次」怎么办？
• 260. 只出现一次的数字 III（延伸）：两个元素各出现一次，其余两次。做法：全体异或得到 x ^ y，取它最低位的 1 作为分组标志，把数组分成两组再各自异或，分别得到 x 和 y。字节面试常考这个进阶版。

169. 多数元素

题意

给定大小为 n 的数组，返回其中的多数元素——出现次数大于 n/2 的元素。题目保证数组中必然存在多数元素。

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

题目本质：Boyer-Moore 投票算法。维护候选 candidate 与票数 count：遇到与候选相等的加一，不等则减一，count 降到 0 就换候选。因为多数元素数量超过一半，最终存活的一定是它。

现实类比：选举计票的「对抗消去」。每遇到一个支持者票数 +1，遇到一个反对者票数 -1，双方相互抵消，最后还没被抵消掉的那个候选人就是多数派。

难点与易错点

1. 为什么抵消后剩下的一定是多数元素：多数元素出现次数 > n/2，意味着它比其余所有元素加起来还多，一对一抵消后它的票数必然为正，不会被完全清空。
2. count == 0 换候选后要立刻把 count 置 1，这个细节漏了就全错。
3. 本题保证多数元素必然存在，所以投票结果无需二次验证；但若面试官改成「不一定存在」，就必须再扫一遍数组统计候选出现次数是否真的 > n/2。
4. 边界：单元素数组 [x] 直接返回 x（源码里 candidate = nums[0] 天然处理了这个情况）。

解法一：暴力 / 直观（HashMap 计数）

统计每个元素出现次数，找到次数 > n/2 的返回。

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        int threshold = nums.length / 2;
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            if (e.getValue() > threshold) {
                return e.getKey();
            }
        }
        return -1; // 按题意不会走到这里
    }
}

复杂度：两遍遍历 O(n) 时间，哈希表 O(n) 空间。

瓶颈：空间 O(n)。此外排序法（排序后取 nums[n/2]）时间 O(n log n) 也非最优。这题的考点是「O(1) 空间找众数」。

解法二：优化 / 最优（Boyer-Moore 投票）

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = nums[0];   // 初始候选为第一个元素
        int count     = 1;         // 票数初始为 1

        for (int i = 1; i < nums.length; i++) {
            if (count == 0) {
                candidate = nums[i];  // 票数清零，更换候选人
                count     = 1;        // 换候选后票数重置为 1
            } else if (nums[i] == candidate) {
                count++;              // 支持票
            } else {
                count--;              // 反对票，相互抵消
            }
        }
        return candidate;             // 多数元素必然最终存活
    }
}

> **💭 思考**：为什么找「出现次数 > n/2 的元素」会想到「投票抵消」而不是继续用哈希计数？一步步想——HashMap 计数是 O(n) 时间但 O(n) 空间，而这题没有 O(1) 空间的硬约束，却给了更关键的信息：多数元素数量**严格过半**。过半意味着它比其余所有元素加起来还多，于是想到「一对一抵消」——用一个候选 + 一个票数，遇到支持者 +1、反对者 -1，双方消耗，最后剩下的必然是数量占优的多数元素。这正是把「统计次数」从「记录每个数的个数」压缩成「只追踪一个净胜票」的巧思，空间从 O(n) 降到 O(1)。

复杂度逐步推导：

• for 循环从 i = 1 到 n - 1，共执行 n - 1 次，每次只有常数次的比较与加减，故 T(n) = (n-1) · O(1) = O(n)，时间复杂度 O(n)。
• 全程只使用 candidate 和 count 两个变量，无论 n 多大都不新增存储，空间复杂度 O(1)。

正确性直觉：把「多数元素」看作 +1 派，其余所有元素看作 -1 派。多数元素数量严格过半，所以「净票数」恒大于 0；即便中途某些非多数元素凑在一起把当前非多数候选的票数抵消干净，它们自己也消耗殆尽，最终存活、票数为正的只会是数量占优的多数元素。

多解法对比

在「出现次数 > n/2 且必然存在」的约束下，摩尔投票用一次遍历就锁定了答案，时间空间双双最优，是该约束下的标准答案。

CodeTop 变体

• 229. 多数元素 II（延伸同套路题）：找出现次数 > n/3 的所有元素（最多两个）。把单候选推广为「两个候选 + 两个计数」，是摩尔投票的直接扩展，阿里、腾讯面试都出现过。
• 字节高频追问：若要求出现次数 > n/k 的元素呢？推广为维护 k-1 个候选与计数器。
• 追问：如果题目不保证多数元素存在，如何保证正确性？—— 摩尔投票选出的候选，还需二次遍历统计其真实出现次数，判断是否 > n/2。

75. 颜色分类

题意

给定一个只包含 0、1、2 的数组（经典的「荷兰国旗」问题），要求原地排序，使 0 全在前、1 全在中、2 全在后，不能使用内置排序函数。

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

题目本质：三指针（荷兰国旗问题）。low 指向 0 区的末尾，high 指向 2 区的开头，i 遍历中间未分类区域：遇到 0 与 low 交换，遇到 2 与 high 交换（i 不前进），遇到 1 直接前进。

现实类比：三色珠子分拣。设红/白/蓝三个区域，从中间区域逐个检查：红色扔到左边，蓝色扔到右边，白色留在原处不动。

难点与易错点

1. 循环条件必须是 i <= high，不是 i < n：high 右边的元素都已经确定是 2，如果遍历到 n，会把已排好的 2 重新换乱。
2. 遇到 2 交换后 i 不前进：因为从 high 换过来的元素是未知的，还需要再判断一次；而遇到 0 交换后 i 可以前进，因为从 low 换过来的元素必然是 1（low..i 之间全部是 1）。
3. low 和 high 的语义别搞混：low 是「0 区末尾 + 1」（即下一个 0 要放的位置），high 是「2 区开头 - 1」（即下一个 2 要放的位置）。
4. 三指针初始化：low = 0、high = n-1、i = 0，三个都从两端与起点出发。

解法一：暴力 / 直观（计数排序，两遍扫描）

先统计 0、1、2 的个数，再按数量重写数组。虽然也 O(1) 空间，但需要两次遍历。

class Solution {
    public void sortColors(int[] nums) {
        int c0 = 0, c1 = 0, c2 = 0;
        // 第一遍：计数
        for (int num : nums) {
            if (num == 0) c0++;
            else if (num == 1) c1++;
            else c2++;
        }
        // 第二遍：按 0、1、2 顺序重写
        int idx = 0;
        while (c0-- > 0) nums[idx++] = 0;
        while (c1-- > 0) nums[idx++] = 1;
        while (c2-- > 0) nums[idx++] = 2;
    }
}

复杂度：两遍遍历 O(n) 时间，O(1) 空间。

瓶颈：时间常数上是「两遍」，且它对「只有三类值」做了硬编码；面试官往往追问「能不能一遍扫完」。

解法二：优化 / 最优（三指针荷兰国旗，一遍扫描）

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, high = nums.length - 1, i = 0;

        while (i <= high) {
            if (nums[i] == 0) {
                swap(nums, i++, low++); // 0 → 左区，i 前进（换来的必是 1）
            } else if (nums[i] == 2) {
                swap(nums, i, high--);  // 2 → 右区，i 不前进（换来的元素未知）
            } else {
                i++;                    // 1 → 中区，直接前进
            }
        }
        // 结束：[0, low) 全 0，[low, high+1) 全 1，(high, n) 全 2
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

> **💭 思考**：为什么「三类值原地排序」要用三个指针而不是两遍计数？一步步想——计数排序两遍扫描已经 O(n)/O(1)，但它的瓶颈是「硬编码三类值、要扫两遍」。想一遍扫完，就必须在单次遍历中同时维护三个区间的边界：`[0, low)` 放 0、`[low, i)` 放 1、`(high, n)` 放 2，中间 `[i, high]` 是未分类区。三个指针各管一个边界：遇到 0 换到左边（`i` 前进，因为换来的一定是已确定的 1）；遇到 2 换到右边（`i` 不前进，因为从 high 换来的元素是未知的，还要再判断）——这个「遇 2 不前进」的不对称，正是三指针一遍扫描能成立的核心。

复杂度逐步推导：

• 观察 i 与 high：i 只增不减，high 只减不增。每次循环，要么 i++，要么 high--，二者之间的区间 (high - i) 每次迭代至少缩小 1；当 i > high 时循环终止。
• 由于 i 最多从 0 走到 n，high 最多从 n-1 退到 -1，两者的总移动次数上界都是 n，所以循环总迭代次数不超过 O(n)。
• 每次迭代只做常数次比较和最多一次交换，故 T(n) = O(n) · O(1) = O(n)，时间复杂度 O(n)（且是一遍扫描）。
• 只用了 low、high、i 三个指针和交换用的临时变量，全部是常数个，空间复杂度 O(1)。

多解法对比

本题约束「原地 + 不能用内置排序」，三指针方案在单次遍历内就把三类元素归位，且无需额外空间，是荷兰国旗问题的标准最优解。

CodeTop 变体

• 四色 / k 色分类（延伸）：把值域从 {0,1,2} 推广到 k 种颜色，三指针不再适用，需要计数排序或桶排序思想；面试常问「颜色种类不确定时怎么办」。
• 两遍双指针版（变体）：先扫一遍把 0 换到最前，再扫一遍把 1 换到中部——思路等价但需要两遍，面试官会追问与一遍版的区别。
• 905. 按奇偶排序数组（同套路）：只分「奇偶两类」的双指针原地划分，是本题的退化版，腾讯面试出现过。

31. 下一个排列

题意

整数数组的「下一个排列」指：把数组重排为字典序中恰好比当前排列大的那个排列；如果当前已经是最大排列（降序），则重排为最小排列（升序）。要求原地修改。

输入：nums = [1,2,3]   →  [1,3,2]
输入：nums = [3,2,1]   →  [1,2,3]
输入：nums = [1,1,5]   →  [1,5,1]

题目本质：从右向左找「下降点」并做最小化更换。具体是三步——从右往左找第一个 nums[i] < nums[i+1] 的位置 i；在 [i+1, n) 中找第一个大于 nums[i] 的元素交换；再把 [i+1, n) 逆转成升序。

现实类比：按字典序翻字典。找到倒数第一个「还可以增大」的位置，换上比它稍大的数，右边尽量排成最小（升序），这样得到的下一个词恰好是字典序里紧跟着的下一个。

难点与易错点

1. 找下降点的条件：从右向左找的是第一个满足 nums[i] < nums[i+1] 的 i（严格小于），而不是「大于」，方向反了会得到上一个排列。
2. 找交换点的条件：在 [i+1, n) 从右向左找第一个 nums[j] > nums[i]（严格大于），因为后缀是降序的，从右往左遇到的第一个大于 nums[i] 的，正是「最小的大于 nums[i]」的元素。
3. 全降序特判：若整个数组是降序（找不到 i，即 i == -1），说明已是最大排列，直接逆转整个数组变成升序。
4. 交换后必须逆转后缀：交换后 [i+1, n) 仍是降序，要逆转成升序才能得到「恰好下一个」的最小排列，漏掉这步会得到错误的较大排列。

解法一：暴力 / 直观（枚举全排列）

最直白的思路是生成数组的全部排列，排序去重后找到当前排列的下一个。

// 伪代码思路：生成全部 n! 个排列 → 排序 → 定位当前排列 → 返回下一项

复杂度：全排列共 n! 个，生成 + 排序的时间 O(n! · n log n!)，空间 O(n!)，在 n = 1000 级别完全不可行。

瓶颈：排列数随 n 阶乘爆炸。这道题不允许枚举，必须利用「字典序下一个排列」的结构性质直接构造。

解法二：优化 / 最优（三步构造）

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

        // 第一步：从右向左找第一个下降位置 i（nums[i] < nums[i+1]）
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) i--;

        if (i >= 0) {
            // 第二步：从右向左找第一个大于 nums[i] 的位置 j，交换
            int j = n - 1;
            while (j > i && nums[j] <= nums[i]) j--;
            swap(nums, i, j);
        }

        // 第三步：逆转 [i+1, n) → 让后缀变为升序（最小排列）
        reverse(nums, i + 1, n - 1);
    }

    private void swap(int[] nums, int a, int b) {
        int tmp = nums[a]; nums[a] = nums[b]; nums[b] = tmp;
    }

    private void reverse(int[] nums, int l, int r) {
        while (l < r) swap(nums, l++, r--);
    }
}

复杂度逐步推导：

• 第一步的 while：i 从 n-2 向左递减，最坏情况（全降序）一直退到 -1，移动 n-1 次，故这一步 O(n)。
• 第二步的 while：j 从 n-1 向左递减，最坏退到 i+1，移动不超过 n-i 次，也是 O(n)。
• 第三步的 reverse：逆转 [i+1, n)，最坏逆转整个数组，交换 n/2 次，O(n)。
• 三步是串行执行的，总时间 T(n) = O(n) + O(n) + O(n) = O(n)，即时间复杂度 O(n)。
• 全程只使用 i、j 及 swap 的临时变量，全部常数个，空间复杂度 O(1)。

多解法对比

在「原地 + 恰好下一个字典序」的约束下，三步构造法单次线性扫描就完成，是 C++ std::next_permutation 的底层实现思路，也是唯一能扛住大 n 的方案。

CodeTop 变体

• 556. 下一个更大元素 III（真实相关题）：把整数看成数字排列，求「恰好比它大的下一个整数」，是本题的数字版，额外要注意 32 位整数溢出，字节面试出现过。
• 上一个排列（prev permutation）（追问）：把两处比较符号反转——找第一个 nums[i] > nums[i+1] 的 i，再找第一个 nums[j] < nums[i] 交换并逆转后缀。
• 46. 全排列 / 47. 全排列 II（同套路延伸）：本题的「逆转 + 交换」思想是生成全排列的基础操作，面试官常顺着问「如何用 nextPermutation 生成全部排列」。

287. 寻找重复数

题意

给定包含 n + 1 个整数的数组 nums，每个整数都在 [1, n] 范围内，有且只有一个整数重复，返回这个重复数。要求不能修改数组，且只使用 O(1) 额外空间。

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

题目本质：Floyd 判圈（快慢指针）。把数组看成链表 i → nums[i]，重复的数字会让链表中出现环，用快慢指针找到入环点，那个入环点就是重复数。

现实类比：电话链追踪。每个号码指向一个新号码（i → nums[i]），重复号码就是两条路径共同指向的节点。快慢指针一路追踪直到相遇，再用同速指针一起走，找到环的入口。

难点与易错点

1. 为什么必然成环：有 n+1 个位置、值域却只有 [1, n]，且只有一个数重复，意味着至少有两个下标指向同一个值，链表必然带环；又因为所有 nums[i] ∈ [1, n]，下标 0 永远不会被任何 nums[i] 指回，所以 0 是环外的头节点。
2. 不能修改数组 → 直接排除排序法；O(1) 空间 → 排除 HashMap/计数数组。
3. 快慢指针的起步与步进：slow = nums[0], fast = nums[0] 起步，用 do-while（先各走一步再判断）；slow 一步 nums[slow]，fast 两步 nums[nums[fast]]，别写成 nums[fast]。
4. 第二阶段重置的起点：找到相遇点后，把 fast 重置为 nums[0]（链表头），而不是 0，然后两指针同速前进，再次相遇处就是入环点（重复数）。

解法一：暴力 / 直观（二分法，不修改数组）

先给出一个满足约束但非最优的方案：对值域 [1, n] 二分，统计数组中小于等于 mid 的元素个数，据此缩小重复数所在区间。

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length - 1;
        int left = 1, right = n;
        while (left < right) {
            int mid = (left + right) >>> 1;
            int cnt = 0;
            for (int num : nums) {
                if (num <= mid) cnt++;   // 统计 <= mid 的个数
            }
            if (cnt > mid) {
                right = mid;             // 重复数在 [left, mid]
            } else {
                left = mid + 1;          // 重复数在 [mid+1, right]
            }
        }
        return left;
    }
}

复杂度：二分共 O(log n) 层，每层遍历一次数组 O(n)，时间 O(n log n)；只用常数变量，空间 O(1)。

瓶颈：虽然不修改数组、O(1) 空间，但时间是 O(n log n)，比快慢指针的 O(n) 慢一档。可作为「想不出快慢指针时的兜底」讲给面试官。

解法二：优化 / 最优（Floyd 快慢指针）

class Solution {
    public int findDuplicate(int[] nums) {
        // 第一阶段：快慢指针找相遇点（证明有环）
        int slow = nums[0], fast = nums[0];

        do {
            slow = nums[slow];          // 慢指针走一步
            fast = nums[nums[fast]];    // 快指针走两步
        } while (slow != fast);

        // 第二阶段：找环的入口（即重复数）
        // 把 fast 重置到链表头，同速前进，再次相遇点就是入口
        fast = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;                    // 即重复数（环的入口）
    }
}

> **💭 思考**：看到「n+1 个数、值域 [1,n]、不改数组、O(1) 空间」，该怎么从「无从下手」走到「快慢指针」？一步步想——排序法会改数组（违规），HashMap/计数数组 O(n) 空间（超限），值域二分 O(n log n)（偏慢）。此时盯住「值都在 [1,n]」这个信号：它意味着 `i → nums[i]` 可以看成一条「下标当边」的链，每个下标指向一个合法位置；而 n+1 个位置、只有 n 个值，必有至少两个下标指向同一个值，链上必然成环，重复数就是环的入口。一旦把数组问题翻译成「链表找环入口」，快慢指针就成了本能选择——这就是 142 题的数组版。

复杂度逐步推导：

• 第一阶段：快慢指针在环内相遇。慢指针每次走 1 步，走到相遇点总步数不会超过「链表头到入口 + 环长」这个量级，上界是 O(n)；快指针步数同样是 O(n) 量级。故第一阶段 O(n)。
• 第二阶段：两指针同速前进，从起点/相遇点走到环入口，距离都不超过 n 步，也是 O(n)。
• 两阶段串行相加，总时间 T(n) = O(n) + O(n) = O(n)，时间复杂度 O(n)。
• 全程只使用 slow、fast 两个指针变量，空间复杂度 O(1)。

为什么第二阶段能定位入口（面试常追问）：设头到入口距离 a，入口到相遇点距离 b，环长 c。相遇时慢指针走了 a + b 步，快指针走了 2(a + b) 步，二者差 a + b 步恰好是环长的整数倍。此时把其中一个指针放回头节点，两指针同速各走 a 步后，会同时在环入口相遇——这正是 142 题「环形链表 II」找入口的标准结论。

多解法对比

本题约束「不改数组 + O(1) 空间」，最自然的 HashMap 和排序都被封死，Floyd 判圈用 O(n)/O(1) 同时满足全部约束，是唯一的最优解。

CodeTop 变体

• 142. 环形链表 II（同套路原型）：给定链表的头节点找入环点，是本题「数组版判圈」的原型，字节面试几乎必问，务必能默写两阶段指针。
• 腾讯 / 阿里追问：为什么慢指针和快指针最终一定会在环内相遇？能否用数学证明第二阶段找入口的正确性？——即上面「a、b、c」的推导。
• 268. 缺失数字（同套路延伸）：[0, n] 中缺一个数，用「异或」或「下标求和」解决，与本题互为镜像（一个找重复、一个找缺失）。
• 41. 缺失的第一个正数（进阶相关）：要求 O(n) 时间 O(1) 空间且原地，用「下标哈希（把值放回应在的位置）」思想，是「不改数组 + 常数空间」类题目的另一座高峰。

结语

「技巧」类题目的价值不在于「背代码」，而在于识别约束 → 匹配套路的映射能力：

面试时先讲清暴力解和它的瓶颈，再自然引出最优解的「题目本质」与「现实类比」，最后逐步推导复杂度——这样即使卡在某个细节，也能让面试官看到你完整的思维链条。

章末提问

1. #136 为什么异或能处理负数、还跟遍历顺序无关？——结论：因为整数在内存里是补码，异或是「按位」运算，跟符号和顺序都无关；由 a^a=0、0^a=a 和交换律/结合律，成对元素两两抵消，剩下的就是单身元素。
2. #169 摩尔投票为什么抵消后剩下的一定是多数元素？要不要二次验证？——结论：因为多数元素数量 > n/2，比其余所有元素加起来还多，一对一抵消后票数必为正、不会被清空。本题保证多数元素存在，无需验证；若题目不保证，则必须再扫一遍统计候选是否真的 > n/2。
3. #287 为什么一定成环，且第二阶段把 fast 重置到 nums[0] 而不是 0？——结论：因为 n+1 个位置、值域只有 [1,n]，至少两个下标指向同一值，必然成环；而所有 nums[i] ∈ [1,n]，0 永远不会被指回，是环外头节点，所以链表头是 nums[0]（下标 0 的值），不是下标 0。