136. 只出现一次的数字——single-number

给你一个 非空 整数数组 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
• 除了某个元素只出现一次以外，其余每个元素均出现两次。

我的错误解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public int singleNumber(int[] nums) {
        int[] result = new int[100000];
        for (int i = 0; i < nums.length; i++) {
            result[nums[i]]++;
        }
        int j = 0;
        while (result[j] != 1) {
            j++;
            if (result[j] == 1) {
                break;
            }
        }
        return j;
    }
}

数组索引越界问题：

• 题目中 nums [i] 可以是负数（范围是 -310⁴ 到 310⁴），而你直接用 nums [i] 作为 result 数组的索引，负数索引会导致数组越界异常。

法一：位运算

如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种。

• 使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字加入集合，如果集合中已经有该数字，则将该数字从集合中删除，最后剩下的数字就是只出现一次的数字。
• 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
• 使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。

上述三种解法都需要额外使用 O(n) 的空间，其中 n 是数组长度。

如何才能做到线性时间复杂度和常数空间复杂度呢？

正确解法（异或运算）：

这道题的最优解是利用 异或运算 的特性：

• 任何数和 0 异或，结果仍是这个数（a ^ 0 = a）
• 相同的数异或结果为 0（a ^ a = 0）
• 异或运算满足交换律和结合律（a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b）

因此，将数组中所有元素依次异或，最终结果就是只出现一次的数字。

1
2
3
4
5
6
7
8
9

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

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度。只需要对数组遍历一次。
• 空间复杂度：O(1)。

法二：使用集合存储数字

利用集合的特性判断数字是否存在，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num)) {
                // 如果集合中已有该数字，说明是第二次出现，移除它
                set.remove(num);
            } else {
                // 如果集合中没有该数字，说明是第一次出现，添加它
                set.add(num);
            }
        }
        // 最后集合中只剩下唯一出现一次的数字
        return set.iterator().next();
    }
}

逻辑说明：

1. 遍历数组中的每个数字，对于每个数字：
   • 如果集合中已经存在该数字，说明它是第二次出现，将其从集合中删除（因为题目中明确其他数字均出现两次）。
   • 如果集合中不存在该数字，说明它是第一次出现，将其加入集合。
2. 遍历结束后，集合中只会剩下那个只出现一次的数字，直接返回即可。

复杂度分析：

• 时间复杂度：O (n)，其中 n 是数组长度，每个元素的添加、删除和查找操作在 HashSet 中平均都是 O (1)。
• 空间复杂度：O (n)，最坏情况下（当唯一元素最后出现时），集合需要存储 n/2 个元素。

我的问题——Set

set是放的时候直接放后面，删怎么删？后面的往前挪吗

我的问题核心是 Set（以常用的 HashSet 为例）的元素存储方式和删除机制，关键结论先明确：

HashSet 既不是 “直接放后面”（无序），删除时也不需要 “后面的往前挪”（底层是哈希表，不是数组），这和你之前学的 ArrayList（动态数组）完全不同！

一、先搞懂：HashSet 根本不是 “有序存储”，何来 “放后面”？

ArrayList 是 动态数组，元素按插入顺序存储在连续的内存空间里（比如索引 0、1、2…），所以 “添加元素到末尾” 是明确的。但 HashSet 底层是 哈希表（数组 + 链表 / 红黑树），元素的存储位置由「哈希值」决定，和插入顺序无关：

1. 当你调用 set.add(num) 时，Java 会先计算 num 的哈希值（比如 num=4 的哈希值是 4）；
2. 根据哈希值计算出它在哈希表数组中的 “索引位置”（比如索引 4）；
3. 把 num 存到这个索引对应的位置（如果该位置已有元素，会以链表 / 红黑树的形式追加，不是数组末尾）。

所以 HashSet 里的元素是 “无序的”，没有 “前面”“后面” 的概念，添加元素也不是 “放后面”，而是 “按哈希值找位置放”。

二、HashSet 删除元素：不需要 “往前挪”，直接定位删除！

正因为底层是哈希表，删除元素的过程和 ArrayList 完全不同：

1. ArrayList 删除的痛点（对比理解）

ArrayList 是连续数组，比如删除索引 2 的元素，后面的索引 3、4、5… 的元素都要往前挪一位（时间复杂度 O (n)），否则会留下空位。

2. HashSet 删除的高效逻辑（核心）

1

set.remove(num); // 删除元素 num

执行步骤：

1. 计算 num 的哈希值，快速定位到它在哈希表数组中的「索引位置」（O (1) 时间）；
2. 遍历该索引位置对应的链表 / 红黑树，找到 num 这个元素（因为可能有哈希冲突，同一索引下可能有多个元素）；
3. 直接将 num 从链表 / 红黑树中移除（O (1) 时间，链表只需修改前后节点的指针，红黑树只需调整结构，无需移动数组元素）。

关键：为什么不用 “往前挪”？

• 哈希表的数组存储的是 “链表 / 红黑树的头节点引用”，不是元素本身；
• 删除元素时，只是修改链表 / 红黑树的节点关系，或者把数组对应位置的引用置为 null（如果该位置没有其他元素了）；
• 数组本身的结构没有变，其他元素的位置也不会动，自然不需要 “往前挪”。

三、举个具体例子（直观理解）

假设 HashSet 的哈希表数组长度为 16，现在存储了元素 [4,1,2]（插入顺序）：

1. add(4)：哈希值 = 4 → 索引 4 → 数组索引 4 存链表头节点（4）；
2. add(1)：哈希值 = 1 → 索引 1 → 数组索引 1 存链表头节点（1）；
3. add(2)：哈希值 = 2 → 索引 2 → 数组索引 2 存链表头节点（2）；

此时哈希表数组的状态（简化）：

当执行 remove(1) 时：

1. 计算 1 的哈希值 = 1 → 定位到索引 1；
2. 遍历索引 1 的链表，找到元素 1；
3. 移除链表中的 1 节点，将数组索引 1 的引用置为 null（因为该位置没有其他元素了）；

删除后的数组状态：

可以看到，删除 1 后，2 和 4 的位置（索引 2、4）完全没动，也没有任何元素 “往前挪”。