从0学习算法-第三天

哈希表

哈希表是根据关键码的值而直接进行访问的数据结构,直白来讲数组就是一张哈希表,哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素。一般哈希表都是用来快速判断一个元素是否出现集合里

常见的三种哈希结构

数组
set(集合)
map(映射)

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

但是哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242.有效的字母异位词

**************************

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

class Solution{
	public boolean isAnagram(String s,String t){
	  int[] record = new int[26];//总共就26个字母
	  
	  for(int i=0;i<s.length();i++){
		record[s.charAt(i)-'a']++;//统计字母出现的次数
	  }
	  for(int i=0;i<t.length();i++){
		record[t.charAt(i)-'a']--;
	  }
	  for(int count:record]{
		if(count!=0)return false;
	  }
	return true;
		  } 
}

349. 两个数组的交集

**************************

题意：给定两个数组，编写一个函数来计算它们的交集。

说明： 输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

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<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
	  //将结果集合转为数组
	  return resSet.stream().mapToInt(x->x).toArray();
	}

1. 两数之和

**************************

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

class Solution {
    //思路:定义一个哈希Map将遍历过的元素存入,然后
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> res=new HashMap<Integer, Integer>();
        for(int i=0;i<nums.length;i++){
            if(res.containsKey(target-nums[i])){
                return new int[][]{res.get(target-nums[i]),i};
            }
            res.put(nums[i],i);
        }
        return new int[0];
    }
}

第454题.四数相加II

**************************

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

class Solution{
	public int forSumCount(int[] nums1,int[] nums2,int[] nums3,int[] nums4){
	  int res=0;
	  Map<Integer,Integer> map=new HashMap<Integer,Integer>();
	  //统计nums1和nums2中的元素之和
	  for(int i:nums1){
		for(int j:nums2){
		  int sum=nums[i]+nums[j];
		  //map.getOrDefault(sum,0)从名为map的映射中获取键为sum的值,如果不存在该键,则返回默认值0
		  //map.getOrDefault(sum,0)+1;//将获取到的值加1;
		  map.put(sum,map.getOrDefault(sum,0)+1);//将键为sum的值加1
		}
		for(int i:nums3){
		  for(int j:nums4){
			res+=map.getOrDefault(0-i-j,0);
		  }
		}
		return res;
	  }
}