• 涉及数组,Set,Map使用
  • 但题目思路大致相同
  • [没必要复习]

代码随想录[原文指路]

概述

1.概述

  • 哈希法牺牲空间换时间

2.作用

  • 快速判断元素是否出现集合里
  • 判断元素是否出现过

3.哈希函数

  • 通过hashCod计算某对象哈希值
  • 该哈希值作为该对象在哈希表中的索引
  • 以便快速找到该对象

4.哈希碰撞

  • 两不同对象计算出的哈希值相同,即索引位置相同

5.解决哈希碰撞

  • 拉链法
    在这里插入图片描述
  • 线性探测法
    在这里插入图片描述

6.常见的哈希结构

  • 数组
  • 集合
  • Map

有效的字母异位词[242]

  • 已知为小写字母,定义一个26位大小的数组存对应字母出现次数
  • 循环s时用+,循环t时用-,最终元素全为0则返回true
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];
        for(char chs:s.toCharArray()){
            record[chs-'a']+=1;
        }
        for(char cht:t.toCharArray()){
            record[cht-'a']-=1;
        }
        for(int n:record){
            if(n!=0) return false;
        }
        return true;
    }
}

两个数组的交集[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<Integer> set2 = new HashSet<>();
        //遍历数组1
        for(int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for(int i : nums2) {
            if(set1.contains(i)) {
                set2.add(i);
            }
        }
        int[] resArr = new int[set2.size()];
        int index = 0;
        //将结果几何转为数组
        for (int i : set2) {
            resArr[index++] = i;
        }
        return resArr;
    }
}

快乐数[202]

class Solution {
    public boolean isHappy(int n) {
        //注意题目中说了会无限循环,所以出现的sum会重复
        List<Integer> list = new ArrayList<>();
        int sum=0;
        while(sum!=1){
            sum=0;
            do{
            	sum += (n%10)*(n%10);
                n /= 10;
            }while(n!=0);
            n=sum;
            if(list.contains(sum)) return false;
            list.add(sum);
        }
        return true;
    }
}

两数之和[1]

  • 暴力
class Solution {
    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]==(target-nums[j])){
					return new int[]{i,j};
				}
			}
		}
		return new int[]{-1,-1};
    }	
}
  • 哈希
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map.containsKey(temp)){
                res[1] = i;
                res[0] = map.get(temp);
            }
            map.put(nums[i], i);
        }
        return res;
    }	
}

四数相加 II[454]

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //统计num12两数之和与出现次数
        Map<Integer,Integer> map1 = new HashMap<>();
        for(int i:nums1) {
            for(int j:nums2) {
                if (map1.containsKey(i + j)) {
                    map1.put(i + j, map1.get(i + j) + 1);
                } else {
                    map1.put(i + j, 1);
                }
            }
        }
        int result=0;
        //与map1相加看是否为0
        Map<Integer,Integer> map2 = new HashMap<>();
        for(int i:nums3) {
            for(int j:nums4) {
                int temp = 0-(i+j);
                if(map1.containsKey(temp)) result+=map1.get(temp);
            }
        }
        return result;
    }
}

赎金信[383]

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        //magazine只能使用一次,当成外层循环
        StringBuffer sb = new StringBuffer(ransomNote);
        for(int i=0;i<magazine.length();i++){
            int index = sb.indexOf(magazine.substring(i,i+1));
            if(index!=-1){
                sb.deleteCharAt(index);
            }
        }
        if(sb.toString()=="")return true;
        return false;
    }
}