认识哈希

一般来说，哈希表都是用来快速判断一个元素是否出现在集合里。
假设需要查询一个名字是否在这所学校里：

  • 枚举的时间复杂度是 O(n)
  • 哈希表的时间复杂度是 O(1)

其中蕴含的原理就是将学生的姓名直接映射为哈希表上的索引，随后通过查询索引下标快速知道这位学生是否在这所学校当中。
常用的三种哈希法的数据结构：

  • 哈希数组
  • set
  • map

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

有效的字母异位词

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

  • 先将 s 中的每个字符映射到一个数组中，用于标志每个字符出现的次数
  • 遍历 t 中所有的字符，将数组中每个字符对应位置的数值减去 1
  • 若流程结束，数组中不全为 0，则返回 false
class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[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;
    }
}

两个数组的交集

力扣题目链接
给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

  • 用 HashSet 解决
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1.length == 0 || nums2.length == 0)
            return new int[] {};
        Set<Integer> set = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        for (int n1 : nums1)
            set.add(n1);
        for (int n2 : nums2) {
            if (set.contains(n2))
                resSet.add(n2);
        }
        int[] resArr = new int[resSet.size()];
        int i = 0;
        for (int e : resSet) {
            resArr[i++] = e;
        }
        return resArr;
    }
}

快乐数

力扣题目链接
编写一个算法来判断一个数 n 是不是快乐数。快乐数定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

  • 无限循环则不是快乐数，本质上是一个判断重复的问题
  • 在替换过程中，若出现了重复的数字（非 1），则说明无限循环
class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }
    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}

两数之和

力扣题目链接
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

  • 遍历每个元素时，首先判断 map 中是否存在 target 减去该元素，若存在则返回；若不存在，则将该元素及其下标存储在 map 中
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];   // 遍历当前元素，并在map中寻找是否有匹配的key
        if(map.containsKey(temp)){
            res[1] = i;
            res[0] = map.get(temp);
            break;
        }
        map.put(nums[i], i);    // 如果没找到匹配对，就把访问过的元素和下标加入到map中
    }
    return res;
}

四数相加Ⅱ

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

  • 首先求出 A 和 B 任意两数之和 sumAB，以 sumAB 为 key，sumAB 出现的次数为 value，存入 hashmap 中
  • 然后计算 C 和 D 中任意两数之和的相反数 sumCD，在 hashmap 中查找是否存在 key 为 sumCD
class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
                int sumAB = A[i] + B[j];
                if (map.containsKey(sumAB))
                    map.put(sumAB, map.get(sumAB) + 1);
                else
                    map.put(sumAB, 1);
            }
        }
        for (int i = 0; i < C.length; i++) {
            for (int j = 0; j < D.length; j++) {
                int sumCD = -(C[i] + D[j]);
                if (map.containsKey(sumCD))
                    res += map.get(sumCD);
            }
        }
        return res;
    }
}

赎金信

力扣题目链接
给你两个字符串 ransomNote 和 magazine，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true；否则返回 false。

  • 与有效字母异位词的区别在于，一个需要 a 和 b 相互组成（字符数量一模一样），另一个只要求 a 能组成 b（ a 的某个字符数必须大于等于 b 的对应字符数）
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : magazine.toCharArray()) {
            cnt[c - 'a']++;
        }
        for (char c : ransomNote.toCharArray()) {
            cnt[c - 'a']--;
            if(cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

分糖果

力扣题目链接
Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i]。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。给你一个长度为 n 的整数数组 candyType，返回：Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的最多种类数。

  • 使用哈希集合，不难想到本题中最多种类数目要么是最多种类数，要么是 n / 2
class Solution {
    public int distributeCandies(int[] candyType) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int candy : candyType) {
            set.add(candy);
        }
        return Math.min(set.size(), candyType.length / 2);
    }
}

最小覆盖子串

力扣题目链接
给你一个字符串 s、一个字符串 t。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “”。

  • 滑动窗口，枚举右侧边界，直到包含 t 中所有字符
  • 随后移动左侧边界，寻找是否有更短的情形
  • 判断是否包含，使用的是哈希数组
  • A ~ Z 是 65 ~ 90
  • a ~ z 是 97 ~ 122
  • int[a] 也就是int[97]
class Solution {
    public String minWindow(String S, String t) {
        char[] s = S.toCharArray();
        int m = s.length;
        int ansLeft = -1;
        int ansRight = m;
        int[] cntS = new int[128];
        int[] cntT = new int[128];
        for (char c : t.toCharArray()) {
            cntT[c]++;
        }
        int left = 0;
        for (int right = 0; right < s.length; right++) {
            cntS[s[right]]++;
            while (isCovered(cntS, cntT)) {
                if (right - left < ansRight - ansLeft) {
                    ansLeft = left;
                    ansRight = right;
                }
                cntS[s[left]]--;
                left++;
            }
        }
        return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
    }
    private boolean isCovered(int[] cntS, int[] cntT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
}