图解算法通识讲义经典套路
位运算与原地数值哈希技巧
核心心智模型：二进制的上帝视角；异或自反消除成双数，数值符号借位实现 O(1) 原地哈希。
核心交互式算法图解演练沙盒
位运算技巧模型
只出现一次的数字与异或 (XOR) 对冲消消乐演练
步骤 1 / 5
当前累积异或和:4(二进制: 0100)
律则：a ^ a = 0，a ^ 0 = a4
目标值
1
成对数字 1
2
成对数字 2
1
成对数字 1
2
成对数字 2
初值异或：0 ^ 4 = 4 (二进制 0100)。
关键操作与时空复杂度速查对照表
| 操作 / 算法阶段 | 平均时间 | 最坏时间 | 空间复杂度 | 核心底层机制 |
|---|---|---|---|---|
| 全量异或消除 | O(N) | O(N) | O(1) | 单次按位计算，无需任何辅助哈希表。 |
| 原地符号标记 | O(N) | O(N) | O(1) | 常数级读写原数组正负号。 |
template.java
int single = 0;
for (int num : nums) {
single ^= num;
}
return single;解题核心心法提炼
- n & (n - 1) 能够瞬间将二进制表示中最低位的 1 抹成 0（汉明重量与 2 的幂判定）。
- 摩尔投票法（多数元素）：同族抱团加票，异族同归于尽，最终存活的候选人必为超过半数的绝对多数。
- 原地哈希利用数组自身作为天然存储，是压榨空间复杂度到 O(1) 的终极利器。
常见踩坑警示与避坑指南
- 原地符号翻转时在后续读取没有加上 Math.abs() 导致数组负数越界。
对应 Hot 100 实战题目突围
原理已掌握！立即进入沉浸式工作台开始实战演练，强化代码肌肉记忆