哈希表¶
link: 代码随想录 哈希表
1. 哈希表相关理论¶
1.1 哈希表定义¶
哈希表定义： 哈希表是根据关键码的值而直接进行访问的数据结构。
即数组就是一张哈希表。哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如图：
使用哈希表的场景：快速判断一个元素是否出现集合里。 （时间复杂度 ）
案例： 查询一个名字是否在这所学校里。 只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。
1.2 哈希函数¶
将学生姓名映射到哈希表上就用到了 hash function ，也就是哈希函数
哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。
哈希函数如图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。
因为哈希表就是一个数组。如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。
1.3 哈希碰撞¶
如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。
解决 哈希碰撞有两种方法：拉链法和线性探测法
1.4 拉链法¶
小李和小王在索引1的位置发生了冲突，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了。
（数据规模是dataSize， 哈希表的大小为tableSize）
拉链法要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。
1.5 线性探测法¶
使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。
例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：
1.6 常见的三种哈希结构¶
- 数组
- set （集合）
- map(映射)
2. 有效的字母异位词¶
link: LeetCode 242
字母异位词：指由相同的字母重新排列而成的单词或短语。换句话说，字母异位词具有相同的字母，但字母的顺序不同。例如，"listen"和"silent"是字母异位词，因为它们由相同的字母组成，只是字母的顺序不同。
方法一：暴力
方法二：哈希表
首先定义一个数组 record 用来记录字符串 s 里每个字符出现的次数。
需要把字符映射到数组(也就是哈希表的索引下标)上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。,即数组长度n=26即可
其次 在遍历 字符串s 的时候，只需要 record[s[i] - 'a'] +1 即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。
然后 在遍历字 符串t 的时候，对t中出现的 字符 映射哈希表索引上的数值再做-1的操作。即 record[s[i] - 'a'] +1
class Solution {
public boolean isAnagram(String s, String t) {
// 定义一个数组 record 记录字符串 s 中每个字符出现的次数
int record[] = new int[26];
// 遍历字符串 s , 将s中的每个字符对应的哈希映射 加1
for (int i=0; i < s.length(); i++){
record[s.charAt(i) - 'a']++;
}
// 遍历字符串 t , 将t中的每个字符对应的哈希映射 -1
for (int i=0; i<t.length(); i++){
record[t.charAt(i) - 'a']--;
}
// 遍历数组 record, 判断是否所有元素都等于0
for (int i=0; i<record.length; i++){
if (record[i] != 0) return false;
}
return true;
}
}
3. 两个数组的交集¶
link : LeetCode 349
思考：
题目关键词：唯一，无序，像这种可以用 HashSet
方法一：使用 HashSet
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1.length==0 || nums2.length==0) return new int[0];
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
for (int i=0; i<nums1.length; i++) set1.add(nums1[i]);
for (int j=0; j<nums2.length; j++) {
if (set1.contains(nums2[j]))
resSet.add(nums2[j]);
}
return resSet.stream().mapToInt(x->x).toArray();
}
}
方法二：使用数组哈希
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// 因为数组内的数值大小在 0-1000, 因此定义 哈希数组的长度为 1010
int a[] = new int[1010];
int b[] = new int[1010];
List<Integer> resList = new ArrayList<>();
// 遍历第一个数组 nums
for (int i=0; i<nums1.length; i++){
a[nums1[i]]+=1;
}
for (int i=0; i<nums2.length; i++){
b[nums2[i]]+=1;
}
for (int i=0; i<1010; i++){
if (a[i] != 0 && b[i] != 0)
resList.add(i);
}
// 因为要返回数组
int res[] = new int[resList.size()];
for (int i=0; i<resList.size();i++){
res[i] = resList.get(i);
}
return res;
}
}
4. 快乐数¶
link : LeetCode 202
思考： 求每个数位上的平方和，这个平方和我们并不知道这个平方和有多大，同时因为这个平方和可能会无限不循环，因此需要判断这个平方和之前是否出现过， 因此用哈希法。
class Solution {
int getSum(int n){
// 定义平方和 sum
int sum=0;
while(n != 0){
int temp = n % 10;
n /= 10;
sum += (temp * temp);
}
return sum;
}
public boolean isHappy(int n) {
Set<Integer> recordSet = new HashSet<>();
while(true){
int sum = getSum(n);
if (sum == 1) return true;
if (recordSet.contains(sum)) return false;
recordSet.add(sum);
n = sum;
}
}
}
5. 两数之和¶
link: LeetCode
思考：
什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
本题中，就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。
我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。
使用数组和set来做哈希法的局限。
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
Java实现：使用 HashMap
class Solution {
public int[] twoSum(int[] nums, int target) {
// 使用map, key: 数组中的值， value：对应的下标
Map<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums.length; i++){
if (map.get(target - nums[i]) != null){
int res[] = {map.get(target - nums[i]), i};
return res;
}else{
map.put(nums[i], i);
}
}
return new int[0];
}
}
6. 四数之和¶
link: LeetCode 454
思考：
题目最终需要的答案：在四个数组中有多少个 元组 满足条件, 即下标对应的元素值相加等于0，因此进行存储的时候不需要存储下标，只需要存储下标对应的元素值的 和
解题步骤：
- 定义一个 Map， key为数组A和数组B 所有元素相加的和（数组A中的每个元素加数组B中的每个元素），value为出现的次数
- 定义 cnt， 存储满足条件的元组个数
- 遍历数组C和数组D，将数组C和数组D中的每个元素相加, 并判断 0-(C[i]+D[j])是否在map中，如果存在，cnt+=map.get(0-(C[i]+D[j])) (此处需要注意不是加1，因为map中存储的对应的key， value并不一定是1，即A和B两个数组中可能不止一对元素相加等于key)
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
Map<Integer, Integer> map = new HashMap<>();
for (int i=0; i<nums1.length; i++){
for (int j=0; j<nums2.length;j++){
int sum = nums1[i] + nums2[j];
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
int cnt = 0;
for (int i=0; i<nums3.length; i++){
for (int j=0; j<nums4.length; j++){
if (map.get(0-nums3[i] - nums4[j])!=null){
cnt += map.getOrDefault(0-nums3[i]-nums4[j], 0);
}
}
}
return cnt;
}
}
7. 赎金信¶
link: LeetCode 383
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
// 使用数组哈希
int a[] = new int[26];
for (int i=0; i<magazine.length(); i++){
a[magazine.charAt(i) - 'a'] += 1;
}
for (int i=0; i<ransomNote.length(); i++){
if (a[ransomNote.charAt(i) - 'a'] != 0){
a[ransomNote.charAt(i) - 'a']--;
}else{
return false;
}
}
return true;
}
}
8. 三数之和(重点看)¶
link : LeetCode 15
注意：题目需要寻找的是满足条件的三元组，是数组中的元素，而不是下标；同时寻找到的三元组不能重复（即使对应下标不同，但是值也不能重复）
思考：如果使用双指针
首先 1 ： 将数组按照从小到大的顺序进行排序
然后 2：外层一个 for 循环遍历数组，遍历到的值作为 a， 同时 定义双指针，\(left = i+1 , right = nums.length-1\), 如图：
之后 3：三元组为 \(a=nums[i], b=nums[left], c=nums[right]\) - 当和大于0，因为数组是排过序的，所以只能 right 左移 减小c的大小, 从而减小整体的和 - 当和小于0，因为数组是排过序的，所以只能 left 右移 减小c的大小, 从而增大整体的和 - 当 \(nums[i] > 0\), 说明最左边的 a 都大于0，那么三元组的和也不可能会等于0，直接跳出循环
然后 4（去重）： - \(a\) 的去重，即对 \(nums[i]\) 进行去重, 当 \(nums[i] == nums[i-1]\) 的时候，直接跳过该元素, 因为在上一步的时候已经对 \(nums[i-1]\) 处理过了，当 \(nums[i] == nums[i-1]\) 的时候，数组已经排序，如果能找到满足条件的三元组，必定和 \(nums[i-1]\) 一样, 因此跳过 \(nums[i]\) - b 和 c 的去重，当 \(nums[left] == nums[left-1]\)，left继续向前，因为 \(nums[left-1]\) 满足条件，而\(nums[left]=nums[left-1]\); 那么根据\(nums[left]\) 必定会找到相同的三元组; 同理 \(nums[right] == nums[right+1]\)，right继续向左
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// 定义存储结果的List
List<List<Integer>> resList = new ArrayList<>();
// 首先使用快排对数组排序
Arrays.sort(nums);
// 首先判断nums的长度，只有大于等于三, 才能找到至少一个三元组
// 同时已经进行排序，第一个数字（最小的数字）只有小于等于0，才能满足条件
if (nums.length < 3 || nums[0] > 0 )return resList;
// 定义两个指针, 一个从左边开始, 一个从右边开始
// 首先从左向右扫描数组, 定义第一个数
// 两个指针分别指向第二个和第三个数
for (int i=0; i<nums.length-1; i++){
// 判断最左边的nums[i]
if (nums[i] > 0) break;
// 对a进行去重
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i+1, right = nums.length-1;
// 如果和小于0, 则left向右移动， 寻找更大的数字
while(left < right){
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0){
// 找到了满足条件的三元组
resList.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 但是可能不止一组
// 比如 -1 -1 1 0 2
// 需要left和right继续前进
left++;
right--;
// 对left和right进行去重
while(left < right && nums[left] == nums[left-1]) left++;
while(left < right && nums[right] == nums[right+1] ) right--;
}
else if (sum < 0) left++;
else if (sum > 0) right--;
}
}
return resList;
}
}
9. 四数之和¶
link: LeetCode 18
思考：使用双指针
参考第8道题：三数之和
四数之和的双指针解法是两层for循环\(nums[i] + nums[j]\)为确定值， 循环内有left和right下标作为双指针，找出\(nums[i] + nums[j] + nums[left] + nums[right] == target\) 的情况。
三数之和的时间复杂度是\(O(n^2)\)，四数之和的时间复杂度是\(O(n^3)\) 。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> resList = new ArrayList<>();
Arrays.sort(nums);
for (int i=0; i<nums.length-3;i++){
// 如果第一个数大于0并且大于target, 则说明之后的数字中没有满足条件的四元组
if (nums[i] > 0 && nums[i] > target) return resList;
// 去除重复
if (i > 0 && nums[i] == nums[i-1]) continue;
for (int j=i+1; j<nums.length-2;j++){
// 去除重复
if (j > i+1 && nums[j] == nums[j-1]) continue;
int left = j+1, right = nums.length-1;
while(left < right){
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum < target) left++;
else if (sum > target) right--;
else if (sum == target){
resList.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
right--;
while(left < right && nums[left] == nums[left-1]) left++;
while(left < right && nums[right] == nums[right+1]) right--;
}
}
}
}
return resList;
}
}