做完题目，总算理解为什么三数之和荣获“初代噩梦”的称号了。真的是对照着题解才能弄明白每一步到底都想干些什么……

454.四数相加II

从四个数组里各挑一个元素，只考察组合而不考察元素的值，无需对结果去重，三种罪导致四数相加II空有四数之名而毫无威慑力。

最暴力的做法就是四个 for 循环将所有元素一个一个一个一个遍历过去，时间复杂度就是 O(n^4) 。这个时间复杂度是相当夸张的，是否存在能够降低时间复杂度的解法？

考虑到只需要返回组合的数量，可以先遍历前两个数组，将其所有可能出现的运算结果及运算结果的出现次数存储在 HashMap 中（需要键值对，长度不固定，其他两种哈希表不可用），再遍历剩下两个数组，如果 0 减去遍历到的两个元素得到的结果出现在了 HashMap 中，就在返回值中加上这个结果对应的 Value 。这种算法只需要运算两次嵌套 for ，时间复杂度为 O(n^2) ，比暴力解法好很多。

import java.util.HashMap;

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> record = new HashMap<>();
        int result = 0;
        
        // 统计 a + b 所有的结果及出现次数
        for (int a : nums1) {
            for (int b : nums2) {
                record.put(a + b, record.getOrDefault(a + b, 0) + 1);
            }
        }

        // 统计 c + d 的情况，如果 (0 - c - d)在Map中出现过就加在 result 里
        for (int c : nums3) {
            for (int d : nums4) {
                if (record.getOrDefault(0 - c -d, 0) > 0) {
                    result += record.get(0 - c - d);
                }
            }
        }

        return result;
    }
}

383. 赎金信

哈希表系列题目最后的仁慈，字母异位词异父异母的亲兄弟，因此难度并不高。唯一需要注意的地方是，与字母异位词不同，即使 magazine 中出现了 ransomNote 不需要的字符也没有问题，只要能够提供满足 ransomNote 字符需要即可。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] count = new int[26];

        for (int i = 0; i < magazine.length(); i++) {
            char c = magazine.charAt(i);
            count[c - 'a']++;
        }

        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            count[c - 'a']--;
            if (count[c - 'a'] < 0) {
                return false;
            }
        }

        return true;
    }
}

15. 三数之和

初代魔王，堂堂登场！

严重怀疑这道题出现在这里的原因只是它能够勉强用哈希表做出来而已。它应该出现在双指针专题里，真的。

这道题，双指针解法是核心精髓，不得不品尝。遍历元素找到符合条件的数只是第一步，结果去重才是这道题的重点难点所在。由于题目不要求返回元素的下标，因此可以对数组进行排序操作。有序数组是使用双指针法的一个前提。

排序后，就可以对结果进行遍历了。暴力的解法依然是 for 循环嵌套，时间复杂度 O(n^3) 。使用双指针，可以少用一个 for ，时间复杂度 O(n^2) 。本题的双指针要干的活就是寻找满足三数之和等于 0 的组合，具体而言，若三数之和大于 0 ，则说明右侧元素过大，需要左移，反之左侧元素过小，需要右移，相等时，记录结果。由于题目要求返回不重复的结果组合，因此需要格外注意在遍历中可能出现的结果重复的情况。具体到本题的解法，需要针对第一层循环遍历到的元素和双指针指向的元素进行判断，如果这个元素和之前遍历到的元素/已经记录在结果组合中的元素相等，就跳过。

太难了，我选择二刷好好消化.jpg

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;  // 去重 #1
            }

            int left = i + 1;
            int right = nums.length - 1;

            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) {
                    right--;  // 结果大于 0 ，右侧元素过大，左移
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    left++;  // 结果小于 0 ，左侧元素过小，右移
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));  // 结果添加至结果集内
                    while (left < right && nums[right - 1] == nums[right]) {
                        right--;  // 去重 #2
                    }
                    while (left < right && nums[left + 1] == nums[left]) {
                        left++;  // 去重 #3
                    }

                    right--;  // 常规左移
                    left++;  // 常规右移
                }
            }
        }

        return result;
    }
}

18. 四数之和

四数之和是三数之和的升级版，但内里的逻辑与三数之和非常相似。与三数之和不同之处在于，四数之和的target没有限制，可以是正数，可以是负数，也可以是 0 ，所以先前用在三数之和内的剪枝操作需要修改。总体而言，四数之和的代码在三数之和的基础上，多添加了一层 for 循环，修改了剪枝条件，其余与三数之和基本没有差别。

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

        for (int k = 0; k < nums.length; k++) {
            if (nums[k] > target && nums[k] > 0 && target > 0) {  // 只有当 1.元素大于 target  2.元素大于 0  3. target > 0 时，才能确定之后的元素不可能再出现在结果集内，才能进行剪枝 
                return result;
            }
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;  // 去重 #1
            }

            for (int i = k + 1; i < nums.length; i++) {

                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;  // 去重 #2
                }
                int left = i + 1;
                int right = nums.length - 1;

                while (left < right) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) left++;  // 去重 #3
                        while (left < right && nums[right] == nums[right - 1]) right--;  // 去重 #4
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}

自身水平有限，本篇博客几乎没有自己的做法，只是对题解的又一遍复述。希望二刷时能够彻底理解！