梦开始的地方
哈希表通常作为一种统计手段（或者一个小模块）去配合其他算法解决问题
一、两数之和
简单
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]提示：
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 只会存在一个有效答案
1.1 暴力起手
作为梦开始的地方，只会暴力系正常现象
不难想到暴力解法：尝试以每个索引为第一个数字，从其开始往后找，判断是否有符合条件的第二个数字
class Solution {
/**
* 1. 两数之和（暴力）
*
* @param nums 提供的数组
* @param target 目标值
* @return 和为目标的元素下标数组
*/
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i,j};
}
}
}
return new int[]{};
}
}执行用时63ms，击败5.34%，复杂度O(N^2)
消耗内存45.67MB，击败63.28%，复杂度O(1)
1.2 哈气
哈希在 java 中通过HashMap和HashSet实现，当题目中暗示：
- 需要统计全部数据（频次、位置、出现次数）
- 与顺序无关，即存在性问题
- 无重复数据
下边是哈希的第一种用法：补数查找
- 一遍扫描：先查后存，避免同元素配对自己
class Solution {
/**
* 1. 两数之和（哈希）
*
* @param nums 提供的数组
* @param target 目标值
* @return 和为目标的元素下标数组
*/
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int[] ans = new int[2];
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
ans[0] = i;
ans[1] = map.get(target - nums[i]);
return ans;
}
map.put(nums[i], i);
}
return ans;
}
}执行用时2ms，击败99.69%，复杂度O(N)
消耗内存46.43MB，击败21.33%，复杂度O(N)
二、字母异位词分组
中等
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
解释：
- 在 strs 中没有字符串可以通过重新排列来形成
"bat"。 - 字符串
"nat"和"tan"是字母异位词，因为它们可以重新排列以形成彼此。 - 字符串
"ate"，"eat"和"tea"是字母异位词，因为它们可以重新排列以形成彼此。
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]仅包含小写字母
2.1 哈气
受哈希先入为主的思维影响，可能会想到用两次哈希
HashMap<HashMap<Character, Integer>, List<String>> result = new HashMap<>();
统计每个字符串的字母以及出现次数作为键，本体塞进值中的List中
这样子是可行的，但是效率太低了
既然是同一批字母的随机排列，可以想到把他们按顺序排列，得到的结果将是一样的，这个就是简化后的键
class Solution {
/**
* 49. 字母异位词分组（哈希）
*
* @param strs 提供的数组
* @return 字母异位词分组
*/
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
// 把 s 排序，作为哈希表的 key
char[] chars = s.toCharArray();
Arrays.sort(chars);
map.computeIfAbsent(new String(chars), _ -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
}执行用时7ms，击败91.97%，复杂度O(nmlogm)
消耗内存48.90MB，击败28.33%，复杂度O(nm)
其中 n 为 strs 的长度，m 为 strs[i] 的长度
三、最长连续序列
中等
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9示例 3：
输入：nums = [1,0,1,2]
输出：3提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
3.1 哈气
先把每个数字放入一个HashSet中
然后for (int num : numSet)遍历它，不断判断是否包含num + 1，存在则继续寻找，当捕存在是判断当前的长度是不是新的最大值
但是这样子的时间复杂度就来到了O(n ^ 2)，例如对于：1，2，3，4，我们第一次遍历了1234，第二次遍历了234，第三次遍历了34
可以发现，后边三次遍历的结果一定不是最优的，从中途开始遍历一定不如从起点开始遍历
❓那么怎么舍去这种中途遍历的情况呢
if (!numSet.contains(num - 1))，如果集合中没有num - 1，说明当前num就是一个新的起点
class Solution {
/**
* 128. 最长连续序列（哈希）
*
* @param nums 提供的数组
* @return 最长连续序列长度
*/
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
numSet.add(num);
}
int maxLen = 0;
for (int num : numSet) {
if (!numSet.contains(num - 1)) {
int curNum = num;
int curLen = 1;
while (numSet.contains(curNum + 1)) {
curNum++;
curLen++;
}
maxLen = Math.max(maxLen, curLen);
}
}
return maxLen;
}
}执行用时29ms，击败85.83%，复杂度O(N)
消耗内存93.90MB，击败25.12%，复杂度O(N)