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

// 通过哈希表查找数组中值为 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 + 1return 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;}
}