09-哈希表

哈希表是采用空间换时间的做法，它是速度是非常快的，因此当需要频繁查找某一个数的时候，就可以使用哈希表来解决。（当然也要考虑到二分查找）

使用哈希表的时候尽量通过数组来模拟哈希表，比如在获取字符串中的字符或者数据范围比较小的情况

题目

LC1. 两数之和

这个和 前缀和 中的一些题目很像，先固定一个数，然后找前面的数，看看是否目标对应的 key 是否存在。

由于最终的返回的结果是下标，因此这里的 key 是表示值，value 是表示下标

public int[] twoSum(int[] nums, int target) {
	// 使用 hash 表来优化
	HashMap<Integer, Integer> map = new HashMap<>();
	int n = nums.length;
	for (int i = 0; i < n; i++) {
		if (map.containsKey(target - nums[i])) return new int[]{map.get(target - nums[i]), i};
		map.put(nums[i], i);
	}

	return new int[]{-1 ,-1};
}

问题

为什么是看前面的数据而不是看后面的数据呢？

因为这个是从前往后遍历的，这样就可以判断一下相关的值有没有，然后再把它放进去，这个是可以在一次循环中执行完，而不是需要特意循环一次。

如果想判断后面的，那么就需要从后往前遍历。

面试题 01.02. 判定是否互为字符重排

可以使用数组来模拟 hash 表，这个数组的下标作为 key, value 表示个数。

s1 对应字符的下标是加1, s2 对应字符的下标减1, 这样就可以使用一个 hash 表来解决这个问题了

public boolean CheckPermutation(String s1, String s2) {
	int n1 = s1.length(), n2 = s2.length();
	if (n1 != n2) return false; // 长度不同，说明一定是不相同的

	int[] hash = new int[26];

	for (int i = 0; i < n1; i++) {
		hash[s1.charAt(i) - 'a']++; // s1 加一
		hash[s2.charAt(i) - 'a']--; // s2 减一
	}

	for (int i = 0; i < 26; i++) {
		if (hash[i] != 0) return false; // 如果不为 0, 那么一定是有不相同的字符
	}
	return true;
}

LC219. 存在重复元素 II

这个也是和 LC1. 两数之和 一样，同样是固定一个下标，找前面的就好。

细节：找到相同元素的时候，把原来的数据给覆盖掉，这个会不会影响结果呢？

不会，因为两个下标的距离是越近越好，覆盖的内容只会更近，因此没有影响

public boolean containsNearbyDuplicate(int[] nums, int k) {
	HashMap<Integer, Integer> hash = new HashMap<>();

	for (int i = 0; i < nums.length; i++) {
		int num = nums[i];
		if (hash.containsKey(num) && (i - hash.get(num) <= k)) return true;
		hash.put(num, i); // 可以直接覆盖掉，因为两个坐标距离是越近越好
	}
	return false;
}

LC49. 字母异位词分组

这个题目是可以通过 hash 表来整理分类，key 是排序后的字符串，value 是排序后列表，里面存储的各个结果。

public List<List<String>> groupAnagrams(String[] strs) {
	HashMap<String, List<String>> hash = new HashMap<>();
	List<List<String>> result = new LinkedList<>();

	for (String str : strs) {
		String sortStr = sort(str); // 排序后的字符串
		if (hash.containsKey(sortStr)) hash.get(sortStr).add(str); // 添加对应的元素
		else {
			List<String> list = new LinkedList<String>();
			list.add(str);
			result.add(list); // 把列表添加到 result 中，这样就不需要重新获取了
			hash.put(sortStr, list);
		}
	}

	return result;
}

private String sort(String str) {
	char[] array = str.toCharArray();
	Arrays.sort(array);
	return new String(array);
}