第三章 哈希表part02

454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和 

454.四数相加II 

思路：采用分为两组，HashMap 存一组，另一组和 HashMap 进行比对。

首先求出 A 和 B 任意两数之和 sumAB，以 sumAB 为 key，sumAB 出现的次数为 value，存入 hashmap 中。

然后计算 C 和 D 中任意两数之和的相反数 sumCD，在 hashmap 中查找是否存在 key 为 sumCD。

算法时间复杂度为 O(n²)。

注意点：hashmap.getOrDefault(sumAB, 0)


class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i : nums1){
            for (int j : nums2){
                 int sumAB = i + j;
                map.put(sumAB, map.getOrDefault(sumAB, 0) + 1);
                // 记录数组1和数组2各元素之和及其出现次数
            }
        }
        int ans = 0;
        for (int i : nums3){
            for (int j : nums4){
                int sumCD = i + j;                
                ans += map.getOrDefault(-sumCD , 0);
                // 数组3和数组4各元素之和若满足条件，取出1、2组合的出现次数，加入ans
            }
        }
        return ans;
    }
}

383. 赎金信 

用一个长度为26的数组还记录magazine里字母出现的次数。

然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 哈希法 数组存magezine里字母出现的次数，再遍历ransomNote做--，数组都>=0即为可以
        int[] abc = new int[26];
        for (char i : magazine.toCharArray()){
            abc[i - 'a']++;
        }
        for (char i : ransomNote.toCharArray()){
            abc[i - 'a']--;
        }
        for (int i : abc){
            if (i < 0){
                return false;
            }
        }
        return true;
    }
}

15. 三数之和 

梦破碎的地方

思路1.哈希解法
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。

把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时，也是这道题目通过率如此之低的根源所在。

思路2.排序+双指针法

先排序

遍历nums[i]，若>0则直接退出遍历，遍历过程去重

双指针left、right

三数之和<0 则left++

三数之和>0 则right--

三数之和==0 则加入结果中，left++ 去重， right-- 去重

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);  // 排序
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++){
            if (nums[i] > 0) break;                         // 三个正数之和不会==0
            if (i > 0 && nums[i] == nums[i - 1]) continue;  // 去重，从i==1开始，与i-1比较
            int left = i + 1, right = nums.length - 1;      // 双指针
            while (left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0){
                    // 左指针右移
                    left++;
                }else if (sum == 0){
                    // 加入结果
                    ans.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                    // 左指针右移，去重
                    left++;
                    while (left < right && nums[left] == nums[left - 1]){
                        left++;
                    }
                    // 右指针左移，去重
                    right--;
                    while (left < right && nums[right] == nums[right + 1]){
                        right--;
                    }
                }else{
                    // 右指针左移
                    right--;
                }
            }
        }
        return ans;
    }
}

18. 四数之和 

思路：

在三数之和的基础上做，i j 两层遍历

left right 双指针

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;     // 去重
            for (int j = nums.length - 1; j > 2; j--) {
                if (j < nums.length - 1 && nums[j] == nums[j + 1]) continue; // 去重
                int left = i + 1, right = j - 1;           // 双指针
                while (left < right) {
                    // int 会溢出
                    long sum = (long) nums[i] + nums[left] + nums[right] + nums[j];
                    if (sum < target) {
                        // 左指针右移
                        left++;
                    } else if (sum == target) {
                        // 加入结果
                        ans.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right], nums[j])));
                        // 左指针右移，去重
                        left++;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        // 右指针左移，去重
                        right--;
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else {
                        // 右指针左移
                        right--;
                    }
                }
            }
        }
        return ans;
    }
}