Leetcoder Day6 | 哈希表part02及总结

语言：Java/C++?

目录

383. 赎金信

第15题. 三数之和

哈希法

双指针

第18题. 四数之和

今日总结

---

给你四个整数数组?nums1、nums2、nums3?和?nums4?，数组长度都是?n?，请你计算有多少个元组?(i, j, k, l)?能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

?提示：

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

本题涉及四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不需要去重。本题符合判断某元素是否存在于数组中，所以优先考虑哈希法。接下来需要思考，用哈希法的什么数据结构来解题。本题可以看到数组中的元素范围较大，用数组下标进行映射会很稀疏浪费空间，因此考虑用set或map。在本题中，我们不仅需要判断数组之和，还要统计次数，涉及到两个值，因此用map结构会更合理。

因为是四个数组：

• 如果将一个数组放入map中计算剩下的三个数组之和，时间复杂度是O(n)+O(n^3)，得到 O(n^3)；
• 如果存两个数组之和，如AB。然后计算两个数组之和，如 CD。时间复杂度为O(n^2)+O(n^2)，得到 O(n^2)；
• 如果存三个数组之和，如 ABC。然后计算一个数组，如 D。时间复杂度为：O(n^3)+O(n)，得到 O(n^3)；

因此综合来看，存放两个数组到map中时间复杂度最低。其实这就变成了在map中存储(a+b)，判断另一个值0-(c+b)是否在map中出现过，跟1.两数之和很类似。

---

383. 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意：

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

这道题实际上是242.有效的字母异位词的更改版，有效字母异位词要求两个字符串能够互相组成，这里要求的是ransom能够由magazine组成即可。

按照题设，每个杂志里的字母不可重复使用。注意到这里只包含小写字母，所以可首选哈希法（用空间换时间），同样定义一个数组record，用来记录字符串magazine里字符出现的次数。字符a到字符z的ASCII是26个连续的数值，然后去判断ransom里的字母是否都存在于magazine中。因为这里元素是有限的考虑用数组来解决。

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

    }
}

这里可以看到跟有效字母异位词的区别就是，如果碰到count<0才是无效的，因为不要求magazine的所有字符都出现在ransom中，因此可以有多余的字母。

---

第15题. 三数之和

给你一个包含 n 个整数的数组?nums，判断?nums?中是否存在三个元素 a，b，c ，使得?a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：?答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

哈希法

这道题乍一看和之前做过的四数相加有点像，将a+b存入map中，然后判断来确定 0-(a+b) 是否在数组里出现过。但是有一个很明显的不同就是，这里要求不重复的三元组。所以本题的难点在于如何去除重复解。哈希法在查找的时候是没有顺序的，因此需要把符合条件的三元组放进vector中，然后再去重，过程较麻烦。

先对整个数组进行排序，然后按顺序遍历，第一个数值判断是否有重复值，因为有序，判断是否和下一个数重复即可。对a去重后，判断第二个元素b，同样方法去重，设置一个集合set，若c即-(a+b)存在于set中，则将当前a,b,c返回；若不存在，存储于set中，后移查找满足条件的c，直到数组结束。

import java.util.Set;
import java.util.HashSet;

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){
                break;  // 排序后第一个元素都大于0，所有元素之和必不为0
            }
            if(i>0 && nums[i]==nums[i-1]){// 注意这里如果是 nums[i]==nums[i+1]可能会越界
                continue;  //三元组中的a去重
            }
            Set<Integer> set=new HashSet<>();  //确定第一个元素后对第二个去重
            for(int j=i+1;j<nums.length;j++){
                if(j>j+2 && nums[j-1]==nums[j-2]&& nums[j]==nums[j-1]){
                    continue; //对元素b去重
                }
                int c=-(nums[i]+nums[j]);
                if(set.contains(c)){//set中有满足的条件c，说明找到了符合条件的组合
                    result.add(List.of(nums[i],nums[j],c));
                    set.remove(c);  //把和c重复的值去掉   
                }
                else{
                    set.add(nums[j]);  //若没有找到c，则将当前第二个元素加入，向后移动
                }

            }
        }
    return result;
    }
}

双指针

可以看到哈希法在去重的操作中有很多细节需要注意。而且有两层for循环，因此还可以考虑使用双指针法，会更高效一些。

依旧先将数组排序，从数组开头进行遍历，设i为a所在的位置，设置left和right双指针，left指向i+1代表b所在的位置，right指向nums.length-1代表c所在位置。

因为是排序后的数组，所以我们会有一套规则：

• 如果nums[i] + nums[left] + nums[right] > 0 就说明此时三数之和大了，所以right下标就应该向左移动，这样才能让三数之和小一些。
• 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。

import java.util.Set;
import java.util.HashSet;

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){
                if(nums[i]+nums[left]+nums[right]==0){
                    result.add(List.of(nums[i], nums[left], nums[right]));
                    while(right>left && nums[right]==nums[right-1]) right--;
                    while(right>left && nums[left]==nums[left+1]) left++;
                    right--;   //不要忘记移动left和right
                    left++;
                }
                else if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                }
                else{
                    left++;
                }
            }
        }
        return result;
        
    }
}

---

第18题. 四数之和

题意：给定一个包含?n 个整数的数组?nums?和一个目标值?target，判断?nums?中是否存在四个元素 a，b，c?和 d?，使得?a + b + c + d?的值与?target?相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例： 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]?

?这里跟三数之和有同样的要求，不可以有重复的元素，因此依然可以采取双指针解法，区别在于四数之和为target而不是固定的0。这里要注意，在和固定为0的时候我们可以先判断nums[i] 是否大于0来筛选出一些条件，但是对于target不可以直接进行这样的剪枝，因为target也有为负数的情况。所以在第一步进行剪枝的时候，我们首先需要加上一些判断条件：设置k指向第一个元素，然后进行剪枝：nums[i]>target且nums[i]>=0时，才返回初始的result，否则需要一步步进行判断。随后设置j指向第二个元素，再一次进行剪枝，随后就和三数之和的思路一样了。

import java.util.Set;
import java.util.HashSet;

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++){
                int sumAB=nums[i]+nums[j];
                if(sumAB>target && sumAB>=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 sumAll=sumAB+nums[left]+nums[right];
                    if(sumAll==target){
                        result.add(List.of(nums[i], nums[j], nums[left],nums[right])); 
                        while(right>left && nums[right]==nums[right-1]) right--;
                        while(right>left && nums[left]==nums[left+1]) left++;
                        right--;
                        left++;
                    }
                    else if(sumAll>target){
                        right--;
                    }
                    else{
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

?? 我一开始在if(nums[i]>target && nums[i]>=0) 或 if(sumAB>target && sumAB>=0) 满足条件时 return result;，结果报错了

原因是如果使用 return result;，代码会直接返回 result 并结束函数，导致后续的迭代无法执行，从而遗漏了可能存在的其他符合条件的四元组。

今日总结

今天遇到了三种n数之和的问题，在做题时一定要看好条件，如果不要求含不重复的元组，使用哈希法会很方便；若对元素有要求，尤其是要求不重复时，使用哈希便会很麻烦，可以考虑双指针来解决。