技巧模块概述

算法题中有一类题目，不依赖传统的 DP、二分或贪心框架，而是需要巧妙的 数学性质 或 指针操作 来达到最优解。这类题目考验的是对数据结构和特定规律的洞察力，一旦掌握技巧，代码往往非常简洁且高效。

本章精选的五道题分别代表了五种不同的算法技巧：

• 136. 只出现一次的数字：异或运算的交换律与结合律。
• 169. 多数元素：Boyer-Moore 投票算法（正负抵消）。
• 75. 颜色分类：荷兰国旗问题（三指针原地分区）。
• 31. 下一个排列：字典序排列的生成规律（双指针反转）。
• 287. 寻找重复数：链表判环（Floyd 判圈算法）在数组上的应用。

1. 只出现一次的数字（LeetCode 136）

题目：给定一个非空整数数组，其中某个元素只出现一次，其余每个元素均出现两次。找出那个只出现一次的元素。要求 O(n) 时间，O(1) 空间。

常规思路：哈希表统计频次，但需要 O(n) 空间。

技巧解法（异或）：利用异或运算的三大性质：

• 交换律：a ^ b ^ c = a ^ c ^ b
• 任何数与 0 异或等于本身：0 ^ a = a
• 任何数与自己异或等于 0：a ^ a = 0

将所有数字进行异或运算，成对出现的数字会抵消为 0，最终剩下的就是只出现一次的数字。

public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}

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

关键点：异或运算是处理"成对出现"问题的杀手锏，不仅限于数字，也可扩展到字符（如找出现奇数次的字符）。

2. 多数元素（LeetCode 169）

题目：给定大小为 n 的数组，找出其中出现次数大于 ⌊n/2⌋ 的元素。要求 O(n) 时间，O(1) 空间。

常规思路：排序后取中位数（O(n log n)），或哈希统计（O(n) 空间）。

技巧解法（Boyer-Moore 投票算法）：核心思想是"正负抵消"。维护一个候选众数 candidate 和一个计数器 count。遍历数组：

• 若 count == 0，将当前元素设为候选。
• 若当前元素等于 candidate，count++，否则 count--。 由于众数数量超过一半，它最终会抵消掉所有非众数并留下来。

public int majorityElement(int[] nums) {
    int candidate = 0, count = 0;
    for (int num : nums) {
        if (count == 0) candidate = num;
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

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

关键点：抵消过程不关心具体抵消了谁，只关心票数差额。该算法只保证众数存在时正确（题目已保证）。

3. 颜色分类（LeetCode 75）

题目：给定包含 0、1、2 的数组，原地排序，使所有 0 在前，1 居中，2 在后。不能使用库函数排序。

常规思路：计数排序（两趟遍历），或快排。

技巧解法（荷兰国旗问题 / 三指针）：维护三个指针：

• p0：指向下一个 0 应该放的位置（从左起）。
• p2：指向下一个 2 应该放的位置（从右起）。
• i：当前遍历指针。

遍历时：

• 若 nums[i] == 0，交换 i 和 p0，i++，p0++。
• 若 nums[i] == 2，交换 i 和 p2，p2--（注意 i 不前进，因为换来的新值还需检查）。
• 若 nums[i] == 1，i++。

public void sortColors(int[] nums) {
    int p0 = 0, p2 = nums.length - 1;
    int i = 0;
    while (i <= p2) {
        if (nums[i] == 0) {
            swap(nums, i, p0);
            i++;
            p0++;
        } else if (nums[i] == 2) {
            swap(nums, i, p2);
            p2--;
        } else {
            i++;
        }
    }
}
private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

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

关键点：遇到 2 时 i 不前进，因为从 p2 换过来的元素可能是 0 或 1，需要下一轮继续处理。

4. 下一个排列（LeetCode 31）

题目：给定整数数组，找出其按字典序排列的下一个更大的排列。若不存在（已是降序），则将其升序排列（最小的排列）。要求原地修改。

技巧解法（字典序规律）：

1. 从右向左找第一个升序对 (i, i+1)，满足 nums[i] < nums[i+1]。此时 i 右侧是降序序列。
2. 再从右向左找第一个大于 nums[i] 的元素 nums[j]。
3. 交换 nums[i] 和 nums[j]。
4. 将 i+1 到末尾的序列反转（因为原本是降序，反转后变成升序，得到最小后缀）。

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i+1]) i--;
    if (i >= 0) {
        int j = nums.length - 1;
        while (j >= 0 && nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    reverse(nums, i + 1, nums.length - 1);
}
private void reverse(int[] nums, int l, int r) {
    while (l < r) swap(nums, l++, r--);
}

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

关键点：找到第一个升序对是关键，它决定了可变动的最高位。若完全降序，直接反转整个数组。

5. 寻找重复数（LeetCode 287）

题目：给定包含 n+1 个整数的数组，数字都在 1~n 之间，只有一个数字重复出现（可能多次），找出这个重复数。要求不修改数组，且只用 O(1) 额外空间。

常规思路：二分答案（O(n log n)），或快慢指针。

技巧解法（Floyd 判圈算法）：将数组视为一个链表，其中 i -> nums[i] 表示节点 i 指向节点 nums[i]。因为存在重复数，所以这个链表中必然存在环。我们使用快慢指针找到环的入口，入口节点就是重复的数字。

public int findDuplicate(int[] nums) {
    int slow = nums[0];
    int fast = nums[0];
    // 第一阶段：找到相遇点
    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);
    // 第二阶段：从头开始，以相同速度走到入口
    slow = nums[0];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

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

关键点：满足 nums[i] 的范围在 1~n 且数组长度 n+1，才能保证将 i 映射到 nums[i] 不会越界（且 0 不会出现在值中，所以从 0 出发一定成环）。入口点就是被两个不同下标指向的值，即重复的数。

五题对比与总结

共同本质：这些技巧题都摆脱了常规的"遍历存储"或"排序"思路，而是深入挖掘问题内在的 数学性质（异或、众数票数）、数据结构关联（数组视为链表）或 排列规则（字典序），从而实现最优的时间和空间复杂度。

应试指南：

• 看到"成对出现找唯一"，想到异或。
• 看到"出现次数超过一半"，想到摩尔投票。
• 看到"三类元素原地排序"，想到荷兰国旗。
• 看到"字典序下一个"，记住"升序对 + 交换 + 反转"三步走。
• 看到"n+1 个数在 1~n 之间找重复"，且不能改数组，想到 Floyd 判圈。