langShift技巧（题单顺序）
热题 100 - 技巧分组（按题单顺序）：136 / 169 / 75 / 31 / 287
本页包含题单「技巧」分组的全部题目，顺序与 list.json 保持一致。
“技巧题”统一抓手（点击展开）
- 位运算（XOR）：
a^a=0、a^0=a、交换律/结合律 → “成对抵消”“只剩唯一”。 - 原地改数组：优先想“用下标当桶/用符号当标记/用区间翻转实现旋转或排列”。
- 环检测：数组里出现“值当 next 指针”的结构时（如 287），优先想到 Floyd 快慢指针。
136. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
最优解（位运算 XOR：成对抵消）
最优解讲解（通俗版 + 推理过程）
- XOR 的三个关键性质：
a ^ a = 0（同一个数异或两次会抵消）a ^ 0 = a- 异或满足交换律/结合律（顺序无关）
- 因为除了一个数只出现一次，其它都出现两次，所以把所有数 XOR 在一起：
- 成对的数字会抵消为 0
- 最终只剩下那个单独出现的数字
- 一趟遍历，空间 (O(1))。
类似题目（成对抵消：XOR/位运算套路）
ans = 0for x in arr: ans ^= x
169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109- 输入保证数组中一定有一个多数元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
最优解（Boyer-Moore 投票：不同就互相抵消）
最优解讲解（通俗版 + 推理过程）
- 多数元素出现次数 > n/2。
- 关键推理：多数元素和“非多数元素”两两抵消，最后剩下的一定是多数元素：
- 维护一个候选
cand和计数cnt。 - 看到同样的数就
cnt++，看到不同的数就cnt--（相当于和候选抵消一对）。 - 当
cnt==0，说明候选已经被抵消完了，换一个新候选继续。
- 维护一个候选
- 因为多数元素比其它所有元素加起来还多，所以最后留下的候选必然是多数元素。
类似题目（投票/抵消思想）
if cnt==0: cand=xcnt += (x==cand ? 1 : -1)
75. 颜色分类
给定一个包含红色、白色和蓝色、共 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.length1 <= n <= 300nums[i]为0、1或2
进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
最优解（荷兰国旗：三指针划分 0/1/2）
最优解讲解（通俗版 + 推理过程）
- 目标是把 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. 下一个排列
整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
- 例如，
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 <= 1000 <= nums[i] <= 100
最优解（从右找下降点 + 换更大一点 + 反转后缀）
最优解讲解（通俗版 + 推理过程）
- 目标：得到“字典序刚好比当前大一点点”的排列（尽量小的更大排列）。
- 关键推理 1：从右往左找第一个上升位置 i：
- 从右往左如果一直是非递增，说明后缀已经是“最大的排列”，要想变大必须动更左边。
- 找到
nums[i] < nums[i+1]的位置 i，表示这里还有“变大空间”。
- 关键推理 2：在右侧后缀里找一个“刚好比 nums[i] 大”的元素交换：
- 为了让整体变大但尽量小，交换的那个元素要尽可能小但又比
nums[i]大。 - 由于后缀是非递增的，从右往左找第一个
> nums[i]就是最合适的。
- 为了让整体变大但尽量小，交换的那个元素要尽可能小但又比
- 关键推理 3：交换后把后缀变成最小：
- 交换后，后缀仍然是非递增的，把它反转成递增，就得到最小后缀，从而整体“最小地变大”。
类似题目（字典序下一个：pivot + swap + reverse suffix）
find pivot ifind successor jswap(i,j)reverse(i+1..end)
287. 寻找重复数
给定一个包含 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 <= 105nums.length == n + 11 <= nums[i] <= nnums中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明
nums中至少存在一个重复的数字? - 你可以设计一个线性级时间复杂度
O(n)的解决方案吗？
最优解（Floyd 判环：把数组当成 next 指针）
最优解讲解（通俗版 + 推理过程）
- 条件：长度 n+1，数字范围 1..n，至少有一个重复。
- 关键建模：把数组当成链表：
- 把“下标”当节点，把
next(i) = nums[i]当指针。 - 因为
next(i)总在 1..n，指针永远不会指向 0 以外的地方，必然进入一个循环。
- 把“下标”当节点，把
- 为什么重复数就是环入口？
- 两个不同下标指向同一个值
d（重复），相当于两条边汇入同一个节点，形成环的入口结构。
- 两个不同下标指向同一个值
- Floyd 两阶段：
- 快慢指针在环内相遇（证明同链表判环）
- 一个从起点走，一个从相遇点走，步速相同，在入口相遇（和 142 的推理同款）
- 好处：不改数组、(O(1)) 空间、(O(n)) 时间。
类似题目（数组判环：i -> nums[i]）
meet = floydMeet()entry = findEntry()