【面试最常考算法】哈希表专题

两数之和

// 通过哈希表查找数组中值为 target-nums[i]的值，即为那“两个整数”。如果不是，则存储哈希表并继续向后比对。
// 哈希表的作用：提高查询效率，存放下标值

class Solution {
    public int[] twoSum(int[] nums, int target) {
       Map<Integer,Integer> map = new HashMap<Integer,Integer>();
       for(int i = 0 ; i < nums.length ; ++i){
        // 判断如果哈希表中存在 target-nums[i]的值，则返回这两个数的下标数组
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};// 之前存入的下标值，现在的下标值。
            }
        // 如果判断失败，则将当前值和下标存入哈希表
        map.put(nums[i],i);
       }

       // 如果没有找到，说明不存在，返回一个空数组(创建数组要使用new)
       return new int[0];
    }
}

缺失的第一个正数

class Solution {
    // 正常思路：将数组所有的数放入哈希表，随后从 1 开始依次枚举正整数，并判断其是否在哈希表中，时间复杂度为 O(N)，空间复杂度为 O(N)
    // 原地哈希+哈希表：
    // 但是要满足时间复杂度为 O(n) 并且只使用常数级别额外空间，我们可以将当前数组视为哈希表。一个长度为 n 的数组，对应存储的元素值应该为 [1, n + 1] 之间，其中还包含一个缺失的元素。

// 我们可以遍历一遍数组，将当前元素放到其对应位置上（比如元素值为 1 的元素放到数组第 0 个位置上、元素值为 2 的元素放到数组第 1 个位置上，等等）。
// 然后再次遍历一遍数组。遇到第一个元素值不等于下标 + 1 的元素，就是答案要求的缺失的第一个正数。
// 如果遍历完没有在数组中找到缺失的第一个正数，则缺失的第一个正数是 n + 1。
// 最后返回我们找到的缺失的第一个正数。
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 第一步：清理数组，将无效值（负数和大于数组长度的值）替换为一个无效值（如 n + 1）
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1; // 用比数组长度大的值替换
            }
        }

        // 第二步：使用索引标记值的存在情况
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            // 只处理有效的值（1 到 n）
            if (num <= n) {
                // 将对应的索引位置的值标记为负数，表示该值存在于数组中
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 第三步：查找第一个缺失的正整数
        for (int i = 0; i < n; i++) {
            // 如果索引位置的值是正数，则该位置对应的正整数缺失
            if (nums[i] > 0) {
                return i + 1; // 返回缺失的正整数
            }
        }

        // 如果所有位置的值都被标记为负数，则说明数组中包含了所有从 1 到 n 的整数
        // 因此缺失的正整数是 n + 1
        return n + 1;
    }
}

最长连续序列

暴力做法有两种思路。

• 第 1 种思路是先排序再依次判断，这种做法时间复杂度最少是 O(nlog⁡2n)O(nlog2n)。
• 第 2 种思路是枚举数组中的每个数 num，考虑以其为起点，不断尝试匹配 num + 1、num + 2、... 是否存在，最长匹配次数为 len(nums)。这样下来时间复杂度为 O(n2)O(n2)。

我们可以使用哈希表优化这个过程。

思路：哈希表

1. 先将数组存储到集合中进行去重，然后使用 curr_streak 维护当前连续序列长度，使用 ans 维护最长连续序列长度。
2. 遍历集合中的元素，对每个元素进行判断，如果该元素不是序列的开始（即 num - 1 在集合中），则跳过。
3. 如果 num - 1 不在集合中，说明 num 是序列的开始，判断 num + 1 、nums + 2、... 是否在哈希表中，并不断更新当前连续序列长度 curr_streak。并在遍历结束之后更新最长序列的长度。
4. 最后输出最长序列长度。

class Solution {
    // public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for(int num : nums ){
            numSet.add(num);
        }
            
        int result = 0; // 最终序列长度
        for(int num : numSet){
            // 如果集合中不存在上一个数，那么就是序列开头
            if(!numSet.contains(num-1)){
                int curr = 1;// 当前序列长度
                int currNum = num; // 当前数字
                while(numSet.contains(currNum+1)){
                    curr+=1;
                    currNum+=1;
                }
            result = Math.max(result , curr);

            }
        }
        return result;
    }
}

只出现一次的数字

class Solution {
    // 使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。
    // 但是使用位运算才能做到线性时间复杂度和常数空间复杂度
    // 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a
    // 任何数和其自身做异或运算，结果是 0，即 a⊕a=0
    // 记住：数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num; // 相当于 single = single ^ num
        }
        return single;
    }
}