算法训练营day06 | {454.四数相加II, 383.赎金信, 15.三数之和，18.四数之和}

第三章哈希表-part02，知识点为哈希表、双指针、去重逻辑训练。

454. 四数相加II

• 题目链接：454. 四数相加II
• 状态：两两数组求和，简化为两数之和即可，简单。

1.1 解题过程

• 这道题给了4个独立的数组，而且不用考虑有重复的4个元素加起来等于0的情况，比较简单。

▶

454. 四数相加II

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int res = 0;
        Map<Integer, Integer> sum1 = new HashMap<>();
        Map<Integer, Integer> sum2 = new HashMap<>();
        int n = nums1.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum1.put(nums1[i] + nums2[j], sum1.getOrDefault(nums1[i] + nums2[j], 0) + 1);
                sum2.put(nums3[i] + nums4[j], sum2.getOrDefault(nums3[i] + nums4[j], 0) + 1);
            }
        }
        
        for(Map.Entry<Integer, Integer> e : sum1.entrySet()) {
            Integer num1 = e.getKey();
            Integer time1 = e.getValue();
            res += time1 * sum2.getOrDefault(-num1, 0);
        }
        
        return res;
    }
}

383. 赎金信

• 题目链接：383. 赎金信
• 状态：本题和《242.有效的字母异位词》是一个思路，简单。

2.1 解题过程

• 注意在统计字符个数之前可以先剪枝一下。
  ▶

  383. 赎金信

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

15. 三数之和

• 题目链接：15. 三数之和
• 文档讲解：代码随想录–15. 三数之和
• 视频讲解：梦破碎的地方！| LeetCode：15.三数之和
• 状态：没做出来。看视频之后写了一版代码，方法是排序+双指针。

3.1 解题过程

• 题目要求找到所有不重复且和为0的三元组，官方题解中讨论了不重复的本质是什么？

  • 保持三重循环的大框架不变；
  • 保证第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
  • 保证第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
  • 也就是说我们枚举的三元组 (a,b,c) 满足a≤b≤c，保证了只有 (a,b,c) 这个顺序会被枚举到，减少了重复。
  • 要实现这一点，我们就要将数组中的元素从小到大进行排序。

• 解决这个问题的第一个关键点，数组排序了；随后第二步考虑对三重循环进行优化，通过双指针的方式，一个递增，一个递减。

• 整体思路有了之后，本题还要注意元素最终可行解的去重问题，比如i去重，什么时候可以跳过，注意是continue；在有序数组下，b和c去重条件又是什么。

• 剪枝操作可以进一步优化一下。

▶

15. 三数之和

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        if(nums.length < 3 || nums[0] > 0) return res;
        for (int i = 0; i < nums.length - 2; i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;  // i去重
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right) {
                if (nums[i] + nums[left] +nums[right] > 0) right--;
                else if (nums[i] + nums[left] +nums[right] < 0) left++;
                else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while(left < right && nums[left] == nums[left+1]) left++;  // b去重
                    while(left < right && nums[right] == nums[right-1]) right--;  // c去重
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

18. 四数之和

• 题目链接：18. 四数之和
• 文档讲解：代码随想录–18. 四数之和
• 视频讲解：难在去重和剪枝！| LeetCode：18. 四数之和
• 状态：本题和三数之和的思路相似，基本上解出来了，但在剪枝操作上出错了。

4.1 解题过程

• 题目要求在同一个数组nums中，避免枚举到重复四元组，就需要保证每一重循环枚举到的元素不小于其上一重循环枚举到的元素，且在同一重循环中不能多次枚举到相同的元素，为了实现要求：

  • 数组先从小到大排序；
  • 同一重循环中，如果当前元素的与上一个元素相同，则跳过当前元素。

• 具体实现过程中，我写的剪枝操作有一点问题，在N数之和里，剪枝只能break/continue，return只能用于整个搜索空间必无解的情况！

▶

18. 四数之和

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

5. 哈希表总结

• 想清楚这三个问题，并在需要快速判断一个数是否曾经出现过时，应立即想到用哈希表解题。
  • 什么时候使用哈希表？
  • 使用数组/Set/还是Map？
  • 往里面存什么？
• N数之和中排序后的去重思想，也是这两天的主要收获之一。

6. Java API小结

• Arrays工具类的使用
  • Arrays.sort(nums): 对一个int数组升序排序；
  • Arrays.asList(T... a): 构造一个固定长度的list对象，好用。