哈希表应用：四数相加 II、赎金信、三数之和与四数之和

示例 1： 输入：ransomNote = "a", magazine = "b" 输出：false

示例 2： 输入：ransomNote = "aa", magazine = "ab" 输出：false

示例 3： 输入：ransomNote = "aa", magazine = "aab" 输出：true

题目链接：LeetCode

思路和有效的字母异位词一样。定义一个长度为 26 的数组，下标表示字母的相对顺序，存储的值是 magazine 中字母出现的频率。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] array = new int[26];
        for (char c : magazine.toCharArray()) {
            array[c - 'a']++;
        }
        for (char d : ransomNote.toCharArray()) {
            array[d - 'a']--;
        }
        for (int count : array) {
            if (count < 0) {
                return false;
            }
        }
        return true;
    }
}

15 三数之和

题目：给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

示例 1： 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

题目链接：LeetCode

这个题的关键难点在于不能输出包含重复的三元组。因此需要去重，先把数组排好序，这样之后去重其实就是跳过相同的数字。

双指针法：

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;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

代码中有几个容易错的点：

1. a 的去重：判断 nums[i] 与 nums[i-1] 是否相同，若相同则跳过。
2. bc 去重的逻辑应放在找到一个三元组之后，对 b 和 c 去重。
3. 最后 bc 去重完了之后还有一个 right-- 和 left++ 操作。

18 四数之和

题目：给你一个由 n 个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]。

示例 1： 输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

题目链接：LeetCode

和三数之和是一个思路，双指针法，但是更复杂。 复杂在于两点：1. 需要再套一层 for 循环；2. 剪枝条件更复杂。

不要判断 nums[k] > target 就返回了，因为 target 是任意值。例如数组是 [-4, -3, -2, -1]，target 是 -10，不能因为 -4 > -10 而跳过。剪枝逻辑变为 nums[k] > target && (nums[k] >= 0 || target >= 0)。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > target && nums[i] >= 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
                    break;
                }
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

总结

哈希表主要用于快速判断元素是否存在于集合中。

三种数据结构：数组、Set、Map 用哈希表的时候要判断哪种数据结构更合适：

1. 有些用 Map 确实可以，但使用 Map 的空间消耗要比数组大一些，因为 Map 要维护红黑树或者符号表，而且还要做哈希函数的运算。
2. 数组和 Set：数组的大小是有限的，受到系统栈空间的限制。如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
3. Map 作为哈希表：数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。Set 是一个集合，里面放的元素只能是一个 Key，而两数之和这道题目，不仅要判断 Y 是否存在而且还要记录 Y 的下标位置，所以 Set 也不能用。Map 是一种<key, value>的结构，可以用 Key 保存数值，用 Value 保存数值所在的下标。

具体情况如何判断，有没有想到用哈希表还需要熟练一点。