Hash表算法

哈希表

理论知识（本文来自于代码随想录摘抄）
- 什么是哈希
- 常见的三种哈希结
- - 数组：
  - set:
  - map:
  - 其他常用方法或者技巧（自己总结的）
- 练习题和讲解
- - 有效的字母移位词
  - 349. 两个数组的交集
  - 1. 两数之和
  - 454. 四数相加 II
  - 15. 三数之和
- 总结

理论知识（本文来自于代码随想录摘抄）

什么是哈希

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：
在这里插入图片描述
那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

常见的三种哈希结

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。
数组
set （集合）
map(映射)

数组：

当目标的范围是已知的，是小的，我们会使用数组。（经常使用，所以少介绍。）

set:

在这里插入图片描述

map:

在这里插入图片描述

其他常用方法或者技巧（自己总结的）

在这里插入图片描述
10，用来判断某个值是否存在哈希表中：containsKey()

if(result.containsKey(temp)){}

练习题和讲解

有效的字母移位词

使用int
前置知识：
字母a-z,A-Z的ASCII码是连续的。
所以’a’-‘a’=0；‘z’-‘a’=25；

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] arr=new int[26];              //用来存储26个字母出现的次数
        for(int i=0;i<s.length();i++){      //字符串用length()方法，数组为length。因为对于字符串，length是方法，数组是内置属性。    
        arr[s.charAt(i)-'a']++;             //charAt(i)获取字符串中i位置的字符。  我们在对于的下标的位置+1.比如出现z，则是'z'-'a',在25这个位置+1.
        };
        for(int i=0;i<t.length();i++){
            arr[t.charAt(i)-'a']--;         //目的同样，在对应位置-1，抵消s字符串中出现的字母。
        };
        for(int a:arr){                     //增强for循环方法。
            if(a!=0){                       //进行判断，如果不等0，证明两个里面的出现字母的数量不一致。
                return false;
            }
        }
        return true;
    }
}

349. 两个数组的交集

349. 两个数组的交集
使用set

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }                   //首先判断是否为空
        Set<Integer> set1 = new HashSet<>();        //使用set可以直接去重
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);    
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {         //contains() 判断这个值是否在哈希表中
                resSet.add(i);
            }
        }
        
        //另外申请一个数组存放setRes中的元素,最后返回数组
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }
        
        return arr;
    }
}

1. 两数之和

1. 两数之和
使用map（需要存放 key value）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个 HashMap 来存储数字及其对应的索引
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        
        // 遍历数组
        for (int i = 0; i < n; i++) {
            // 计算当前元素的补数
            int temp = target - nums[i];
            // 检查补数是否在 HashMap 中
            if (map.containsKey(temp)) {
                // 找到结果，那么返回当前索引和补数的索引
                return new int[]{map.get(temp), i};
            }
            // 如果没有找到补数，就把当前数字和它的索引放入 HashMap
            map.put(nums[i], i);
        }
        // 如果没有找到，返回一个空数组，考虑到题目保证有解这里可以省略
        return new int[]{};
    }
}

454. 四数相加 II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        //不仅要保存值，还需要保存其出现次数，所以使用map(key,value)来进行存储数据。
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);//getOrDefault这个的意思是，如果存在，返回存在的值，不存在返回default0
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                //因为本题不去重，所以有不同组合，需要统计的值为 res+sum(对应的值);
                res += map.getOrDefault(0 - i - j, 0);
            }
        }
        return res;
    }
}

15. 三数之和

使用哈希集合：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> result = new ArrayList<>();
	Arrays.sort(nums);

	for (int i = 0; i < nums.length; i++) {
		// 如果第一个元素大于零，不可能凑成三元组
		if (nums[i] > 0) {
			return result;
		}
		// 三元组元素a去重
		if (i > 0 && nums[i] == nums[i - 1]) {
			continue;
		}

		HashSet<Integer> set = new HashSet<>();
		for (int j = i + 1; j < nums.length; j++) {
			// 三元组元素b去重
			if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) {
				continue;
			}

			int c = -nums[i] - nums[j];
			if (set.contains(c)) {
				result.add(Arrays.asList(nums[i], nums[j], c));
				set.remove(c); // 三元组元素c去重
			} else {
				set.add(nums[j]);
			}
		}
	}
	return result;
    }
}

使用双指针（更为推荐）

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //二维集合，因为不止一个集合
            List<List<Integer>> ans=new ArrayList();
            int len=nums.length;

        //如果值小于3，则没有意义
            if(len<3||nums==null) return ans;

        //排序，更方便我们双指针的移动
            Arrays.sort(nums);

        //定i的位置，然后动left和right两个指针的位置来凑0
        for(int i=0;i<len;i++){
        //如果第一个i都>0，则不可能三数之和为0
            if(nums[i]>0) break;
        //题目去重，所以我们判断前一位值如果等于后一位，则跳过。
            if(i>0&&nums[i]==nums[i-1]) continue;
        //定义左右指针    
            int L=i+1;
            int R=len-1;   
            while(L<R){
                int sum =nums[i]+nums[R]+nums[L];
        //如果相等，则添加进入二维数组中
                if(sum==0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
        //归零
                    while(L<R&& nums[L]==nums[L+1]) L++;
                    while(L>R&& nums[R]==nums[R-1]) R--;
                    L++;
                    R--;
                }
        //和小，就左指针右移，和大，就右指针左移
                else  if(sum<0)L++;
                else if(sum>0)R--;
            }
        }
        //返回二维数组。
        return ans;
    }
}