对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎
LeetCode 136. 只出现一次的数字
1. 题目描述
1.1 问题陈述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
要求:
- 算法应具有线性时间复杂度 O(n)。
- 尽量不使用额外空间，即实现常数空间复杂度 O(1)。
2. 问题分析
2.1 输入输出分析
输入为一个整数数组nums，输出为该数组中唯一一个只出现一次的整数。数组保证非空，且除一个元素外，所有元素都恰好出现两次。
2.2 约束条件分析
- 数组长度 n 满足 1 ≤ n ≤ 3 * 10^4，但算法需适应任意规模。
- 元素为整数，范围可能包括负数和大数，但JavaScript中数字类型可安全处理。
- 核心挑战：在 O(n) 时间和 O(1) 空间内解决，排除暴力搜索或排序等低效方法。
3. 解题思路
3.1 思路一：使用哈希表
遍历数组，用哈希表记录每个数字的出现次数，再查找次数为1的数字。时间复杂度 O(n)，空间复杂度 O(n)。
3.2 思路二：使用集合和数学
利用 Set 去重，计算集合元素和的两倍与数组总和的差。由于其他元素出现两次，差值即为目标。时间复杂度 O(n)，空间复杂度 O(n)。
3.3 思路三：使用异或运算（最优解）
利用异或位运算的性质：
- a ^ a = 0（相同数字异或归零）
- a ^ 0 = a（任何数与0异或不变）
- 异或满足交换律和结合律
遍历数组，对所有元素进行异或，成对数字抵消，最终结果即为只出现一次的数字。时间复杂度 O(n)，空间复杂度 O(1)，是最优解。
4. 各思路代码实现
4.1 思路一代码实现（哈希表）
/** * 使用哈希表统计频率 * 步骤： * 1. 创建哈希表（Map）记录每个数字的出现次数。 * 2. 遍历数组，更新哈希表计数。 * 3. 遍历哈希表，返回计数为1的数字。 * 时间复杂度：O(n)，遍历数组和哈希表各一次。 * 空间复杂度：O(n)，哈希表存储最多 n/2 + 1 个键值对。 */varsingleNumber=function(nums){// 创建哈希表，使用 Map 以支持任意整数键constfreqMap=newMap();// 第一次遍历：统计每个数字的出现次数for(letnumofnums){// 如果 num 已存在，计数加1；否则初始化为1freqMap.set(num,(freqMap.get(num)||0)+1);}// 第二次遍历：查找出现一次的数字for(let[num,count]offreqMap){if(count===1){returnnum;// 找到目标}}// 根据题目保证，此处不会执行，但为代码完整性返回-1return-1;};4.2 思路二代码实现（集合和数学）
/** * 使用集合和数学公式 * 步骤： * 1. 使用 Set 去重，得到所有不重复数字。 * 2. 计算 Set 中所有数字的和（setSum）。 * 3. 计算数组所有数字的和（arraySum）。 * 4. 应用公式：目标 = 2 * setSum - arraySum。 * 时间复杂度：O(n)，遍历数组和集合各一次。 * 空间复杂度：O(n)，Set 存储最多 n/2 + 1 个元素。 */varsingleNumber=function(nums){// 创建 Set 去重constnumSet=newSet(nums);// 计算 Set 中数字的和letsetSum=0;for(letnumofnumSet){setSum+=num;}// 计算数组所有数字的和letarraySum=0;for(letnumofnums){arraySum+=num;}// 公式推导：设目标为 x，其他数字各出现两次，则 setSum = x + 其他数字和，arraySum = x + 2 * 其他数字和// 因此，x = 2 * setSum - arraySumreturn2*setSum-arraySum;};4.3 思路三代码实现（异或运算）
/** * 使用异或运算（最优解） * 步骤： * 1. 初始化结果变量为0（因为 0 ^ a = a）。 * 2. 遍历数组，对每个元素执行异或操作。 * 3. 由于异或性质，出现两次的数字相互抵消，最终结果即为只出现一次的数字。 * 时间复杂度：O(n)，仅一次遍历。 * 空间复杂度：O(1)，只使用一个变量。 */varsingleNumber=function(nums){letresult=0;// 初始化为0，不影响异或结果// 遍历数组，累加异或for(letnumofnums){result^=num;// 等价于 result = result ^ num}// 示例说明：假设 nums = [4,1,2,1,2]// 初始 result = 0// 步骤1: result = 0 ^ 4 = 4// 步骤2: result = 4 ^ 1 = 5// 步骤3: result = 5 ^ 2 = 7// 步骤4: result = 7 ^ 1 = 6// 步骤5: result = 6 ^ 2 = 4// 最终返回 4，即目标数字returnresult;};5. 各实现思路的复杂度、优缺点对比表格
| 思路 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 哈希表 | O(n) | O(n) | 直观易懂，可扩展统计任意出现次数 | 需要额外空间，不满足常数空间要求 |
| 集合和数学 | O(n) | O(n) | 利用数学技巧，代码简洁 | 需要额外空间，可能受数字溢出影响（JavaScript 中数字安全） |
| 异或运算 | O(n) | O(1) | 最优解，满足所有要求，代码极简 | 仅适用于其他元素出现偶数次的情况 |
6. 总结
6.1 通用解题模板或思路
此类“找出唯一出现次数不同的元素”问题，通用解题模式包括：
- 哈希表计数：适用于元素频率统计，是前端处理数据的常见方法（如统计用户行为）。
- 位运算：当其他元素出现偶数次时，异或是王牌解法；对于奇数次，可结合位掩码扩展。
- 数学方法：利用和、差、积等性质，但需注意数值范围。
- 排序后比较：但时间复杂度 O(n log n)，不推荐用于线性要求场景。
在前端开发中，这些思路可应用于状态管理、数据去重、性能优化等场景，例如在 Vue/React 中处理大型数组时，异或运算能高效找出差异项。
6.2 LeetCode中类似题目推荐
- LeetCode 137. 只出现一次的数字 II：元素出现三次，找出一次的元素。需用位运算或数学进阶。
- LeetCode 260. 只出现一次的数字 III：两个元素出现一次，其余出现两次。需异或后分组处理。
- LeetCode 268. 缺失数字：从 0 到 n 的序列中找出缺失数。可用异或或求和。
- LeetCode 389. 找不同：字符串中找多余字符。本质相同，可用异或或哈希表。
