技巧（题单顺序）

本页包含题单「技巧」分组的全部题目，顺序与 list.json 保持一致。

“技巧题”统一抓手（点击展开）

位运算（XOR）：a^a=0、a^0=a、交换律/结合律 → “成对抵消”“只剩唯一”。
原地改数组：优先想“用下标当桶/用符号当标记/用区间翻转实现旋转或排列”。
环检测：数组里出现“值当 next 指针”的结构时（如 287），优先想到 Floyd 快慢指针。

136. 只出现一次的数字

力扣原题：136. 只出现一次的数字

Easy

位运算

数组

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

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

输出：1

示例 2 ：

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

输出：4

示例 3 ：

输入：nums = [1]

输出：1

提示：

1 <= nums.length <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴
除了某个元素只出现一次以外，其余每个元素均出现两次。

最优解（位运算 XOR：成对抵消）

正在加载编辑器...

Rust 参考（点击展开）

fn single_number(nums: Vec<i32>) -> i32 {
    nums.into_iter().fold(0i32, |a, b| a ^ b)
}

fn main() {
    println!("{}", single_number(vec![2, 2, 1]));           // 1
    println!("{}", single_number(vec![4, 1, 2, 1, 2]));    // 4
    println!("{}", single_number(vec![1]));                 // 1
    println!("{}", single_number(vec![0, 0, 7]));          // 7
    println!("{}", single_number(vec![-1, -1, -2]));       // -2
}

最优解讲解（通俗版 + 推理过程）

XOR 的三个关键性质：
- a ^ a = 0（同一个数异或两次会抵消）
- a ^ 0 = a
- 异或满足交换律/结合律（顺序无关）
因为除了一个数只出现一次，其它都出现两次，所以把所有数 XOR 在一起：
- 成对的数字会抵消为 0
- 最终只剩下那个单独出现的数字
一趟遍历，空间 (O(1))。

类似题目（成对抵消：XOR/位运算套路）

ans = 0
for x in arr: ans ^= x

169. 多数元素

力扣原题：169. 多数元素

Easy

数组

哈希表

分治

计数

排序

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

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

示例 2：

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

提示：

n == nums.length
1 <= n <= 5 * 10⁴
-10⁹ <= nums[i] <= 10⁹
输入保证数组中一定有一个多数元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

最优解（Boyer-Moore 投票：不同就互相抵消）

正在加载编辑器...

Rust 参考（点击展开）

fn majority_element(nums: Vec<i32>) -> i32 {
    let mut cand = 0i32;
    let mut cnt = 0i32;
    for x in nums {
        if cnt == 0 {
            cand = x;
            cnt = 1;
        } else if x == cand {
            cnt += 1;
        } else {
            cnt -= 1;
        }
    }
    cand
}

fn main() {
    println!("{}", majority_element(vec![3, 2, 3]));                    // 3
    println!("{}", majority_element(vec![2, 2, 1, 1, 1, 2, 2]));         // 2
    println!("{}", majority_element(vec![1]));                          // 1
    println!("{}", majority_element(vec![1, 1, 2]));                       // 1
    println!("{}", majority_element(vec![6, 5, 5]));                    // 5
}

最优解讲解（通俗版 + 推理过程）

多数元素出现次数 > n/2。
关键推理：多数元素和“非多数元素”两两抵消，最后剩下的一定是多数元素：
- 维护一个候选 cand 和计数 cnt。
- 看到同样的数就 cnt++，看到不同的数就 cnt--（相当于和候选抵消一对）。
- 当 cnt==0，说明候选已经被抵消完了，换一个新候选继续。
因为多数元素比其它所有元素加起来还多，所以最后留下的候选必然是多数元素。

类似题目（投票/抵消思想）

if cnt==0: cand=x
cnt += (x==cand ? 1 : -1)

75. 颜色分类

力扣原题：75. 颜色分类

Medium

数组

双指针

排序

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你能想出一个仅使用常数空间的一趟扫描算法吗？

最优解（荷兰国旗：三指针划分 0/1/2）

正在加载编辑器...

Rust 参考（点击展开）

fn sort_colors(mut nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    if n == 0 {
        return nums;
    }
    let mut low = 0usize;
    let mut mid = 0usize;
    let mut high = n - 1;
    while mid <= high {
        match nums[mid] {
            0 => {
                nums.swap(low, mid);
                low += 1;
                mid += 1;
            }
            1 => mid += 1,
            _ => {
                if mid < high {
                    nums.swap(mid, high);
                    high -= 1;
                } else {
                    break;
                }
            }
        }
    }
    nums
}

fn main() {
    println!("{:?}", sort_colors(vec![2, 0, 2, 1, 1, 0]));
    println!("{:?}", sort_colors(vec![2, 0, 1]));
    println!("{:?}", sort_colors(vec![0]));
    println!("{:?}", sort_colors(vec![1, 1, 1, 0, 2, 0]));
    println!("{:?}", sort_colors(vec![2, 2, 2, 1, 0]));
}

最优解讲解（通俗版 + 推理过程）

目标是把 0、1、2 原地排序。
关键推理：用三个指针把数组分成四段（见代码注释）：
- low：下一个 0 应该放的位置
- high：下一个 2 应该放的位置
- mid：当前正在看的元素
遇到：
- 0：和 low 交换，low 和 mid 都前进（因为交换过来的 mid 位置一定是 1 区或已处理过）
- 1：mid 前进
- 2：和 high 交换，high 后退，但 mid 不动（因为换过来的新值还没处理）

类似题目（三路划分：< pivot / == pivot / > pivot）

while (mid <= high):
  if a[mid] < p: swap(low, mid); low++; mid++
  else if a[mid] == p: mid++
  else: swap(mid, high); high--

31. 下一个排列

力扣原题：31. 下一个排列

Medium

数组

双指针

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

最优解（从右找下降点 + 换更大一点 + 反转后缀）

正在加载编辑器...

Rust 参考（点击展开）

fn next_permutation(mut nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    if n <= 1 {
        return nums;
    }
    let mut i: i32 = n as i32 - 2;
    while i >= 0 && nums[i as usize] >= nums[(i + 1) as usize] {
        i -= 1;
    }
    if i >= 0 {
        let mut j = n - 1;
        while nums[j] <= nums[i as usize] {
            j -= 1;
        }
        nums.swap(i as usize, j);
    }
    let l = if i < 0 { 0 } else { (i + 1) as usize };
    let mut a = l;
    let mut b = n - 1;
    while a < b {
        nums.swap(a, b);
        a += 1;
        b -= 1;
    }
    nums
}

fn main() {
    println!("{:?}", next_permutation(vec![1, 2, 3]));
    println!("{:?}", next_permutation(vec![3, 2, 1]));
    println!("{:?}", next_permutation(vec![1, 1, 5]));
    println!("{:?}", next_permutation(vec![1, 3, 2]));
    println!("{:?}", next_permutation(vec![2, 3, 1, 3, 3]));
}

最优解讲解（通俗版 + 推理过程）

目标：得到“字典序刚好比当前大一点点”的排列（尽量小的更大排列）。
关键推理 1：从右往左找第一个上升位置 i：
- 从右往左如果一直是非递增，说明后缀已经是“最大的排列”，要想变大必须动更左边。
- 找到 nums[i] < nums[i+1] 的位置 i，表示这里还有“变大空间”。
关键推理 2：在右侧后缀里找一个“刚好比 nums[i] 大”的元素交换：
- 为了让整体变大但尽量小，交换的那个元素要尽可能小但又比 nums[i] 大。
- 由于后缀是非递增的，从右往左找第一个 > nums[i] 就是最合适的。
关键推理 3：交换后把后缀变成最小：
- 交换后，后缀仍然是非递增的，把它反转成递增，就得到最小后缀，从而整体“最小地变大”。

类似题目（字典序下一个：pivot + swap + reverse suffix）

find pivot i
find successor j
swap(i,j)
reverse(i+1..end)

287. 寻找重复数

力扣原题：287. 寻找重复数

Medium

位运算

数组

双指针

二分查找

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

示例 2：

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

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

提示：

1 <= n <= 10⁵
nums.length == n + 1
1 <= nums[i] <= n
nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

最优解（Floyd 判环：把数组当成 next 指针）

正在加载编辑器...

Rust 参考（点击展开）

fn find_duplicate(nums: Vec<i32>) -> i32 {
    let mut slow = nums[0] as usize;
    let mut fast = nums[0] as usize;
    loop {
        slow = nums[slow] as usize;
        fast = nums[nums[fast] as usize] as usize;
        if slow == fast {
            break;
        }
    }
    let mut p = nums[0] as usize;
    let mut q = slow;
    while p != q {
        p = nums[p] as usize;
        q = nums[q] as usize;
    }
    nums[p]
}

fn main() {
    println!("{}", find_duplicate(vec![1, 3, 4, 2, 2]));                    // 2
    println!("{}", find_duplicate(vec![3, 1, 3, 4, 2]));                    // 3
    println!("{}", find_duplicate(vec![1, 1]));                             // 1
    println!("{}", find_duplicate(vec![1, 1, 2]));                          // 1
    println!("{}", find_duplicate(vec![2, 5, 9, 6, 9, 3, 8, 9, 7, 1]));     // 9
}

最优解讲解（通俗版 + 推理过程）

条件：长度 n+1，数字范围 1..n，至少有一个重复。
关键建模：把数组当成链表：
- 把“下标”当节点，把 next(i) = nums[i] 当指针。
- 因为 next(i) 总在 1..n，指针永远不会指向 0 以外的地方，必然进入一个循环。
为什么重复数就是环入口？
- 两个不同下标指向同一个值 d（重复），相当于两条边汇入同一个节点，形成环的入口结构。
Floyd 两阶段：
1. 快慢指针在环内相遇（证明同链表判环）
2. 一个从起点走，一个从相遇点走，步速相同，在入口相遇（和 142 的推理同款）
好处：不改数组、(O(1)) 空间、(O(n)) 时间。

类似题目（数组判环：i -> nums[i]）

meet = floydMeet()
entry = findEntry()

技巧（题单顺序）

136. 只出现一次的数字

169. 多数元素

75. 颜色分类

31. 下一个排列

287. 寻找重复数

On this page