代码随想录打卡 Day 4

5.四数相加II

leetcode题号:454.四数相加

【题目描述】

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

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

【思路分析】

本题的暴力解可以直接使用四个for循环求解，时间复杂度位$O(n^4)$。

同时，本题可以使用哈希表进行求解，思路如下:

1. 首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4. 再遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5. 最后返回统计值 count 就可以了

依照上述的思路，可以得到下面的代码:

int fourSumCount(vector<int>& A, vector<int> & B, vector<int>& C, vector<int>& D) {
    unordered_map<int,int> umap;

    for(int a:A)
        for(int b:B)
            umap[a+b]++; //建立一个和的哈希表，记录和出现的次数

    int count=0;

    for (int c:C)
        for(int d:D)
            if(umap.find(-c-d)!=umap.end())
                count+=umap[-c-d];  //如果存在相反数，则加到count中

    return count;
}

通过哈希法，本解法的时间复杂度位$O(n^{2)$,空间复杂度位$O(n}2)$.

6. 赎金信

leetcode题号:383:赎金信

【题目描述】

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

【思路分析】

本题与有效字母异位词很像，思路上基本一致。

但本体需要注意的是:

• 杂志中的字母不可重复使用
• 本题只有小写字母

依然可以使用哈希解进行求解。但本题需要注意，由于元素范围已知有限，我们可以直接使用数组维护一个哈希表，而不使用map。map数据结构的底层需要维护红黑树或哈希表，并且需要一个哈希函数，比较费时。在数据量更大是，则会体现出差别。因此本题可以直接使用数组维护较好。

本题的解法如下:

bool canCanstruct(string ransomNote, string magazine) {
    
    int record[26] = {0};

    if(ransomNote.size() > magazine.size()) //比较两者长度
        return false;

    for(int i = 0; i < magazine.size(); i++)

        record[magazine[i] - 'a']++;

    for(int i = 0; i < ransomNote.size(); i++) //遍历ransomNote，如果record中对应的字符个数小于0，则返回false
        record[ransomNote[i] - 'a']--;

    for(int i = 0; i < 26; i++)  //遍历record，如果record中对应的字符个数小于0，则返回false
        if(record[i] < 0)
            return false;
}

7. 三数之和

【题目描述】

leetcode题号:15,三数之和

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

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

【思路分析】

本题并没有要求返回数组的索引值，仅需要返回三元组，因此我们可以先对给出的数组进行排序。

哈希表解法

使用两层``for`循环可以确定a和b的值，然后使用哈希法确定-(a+b)是否在题目中说过

。但是，本题要求答案不包括重复的三元组。如果将去重考虑进去，对于map数据结构来说，是比较费时间的。

双指针法

首先可以将该数组进行排序，使用for循环，i从数组下标0开始，同时定义left和``right指针，起始位置在(i+1)和数组结尾的位置上。这里，我们让a=nums[i],b=nums[left],c=nums[right]`;

如果sum=a+b+c>0,则让right指针向前移动;sum<0时，则让left指针向后移动。按照此思路，后面的关键就是如何对这一方法进行去重。

去重的基本思路

a的去重:

a是nums遍历的元素，如果a出现重复，应当直接跳过。

但这里，有一个问题，判断方法是是判断nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。

需要注意的是，本题中，要求不能有重复的三元组，但是三元组内的元素是可以重复的

因此，应该是判断nums[i]与nums[i-1]是否相同。

b和c的去重:

b和c的去重类似于a的去重，但是本题应当注意，去重的逻辑应当放在找到一个三元数组后，对b和c去重。否则，看如下的一个例子:

$${0，0，0}$$

在这个例子中，如果在获得三元数组前进行对b和c的去重之后，则不会得到正确的结果。

代码

本题的代码如下所示:

vector<vector<int>> threeSum(vector<int>& nums){
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size() - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的数字


        if(nums[i]>0) break; //num

        int left = i + 1; int right = nums.size() - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                while (left < right && nums[left] == nums[left + 1]) left++; // 对left指针去重

                while (left < right && nums[right] == nums[right - 1]) right--; //对right指针去重
//注意去重要在获得三元组结果之后
                left++; right--; //找到对应的三元组后，双指针移动 
            }
            if(sum < 0) left++; //sum<0
            if(sum > 0) right--; //sum>0


        }
    }
}

8. 四数之和

【题目描述】

leetcode题号: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] ]

【思路分析】

与上题类似，本题可以先使用两个for循环nums[i]+nums[j]，再使用一个双指针法找到nums[i]+nums[j]+nums[left]+nums[right]的处理。本题的时间复杂度为$O(n^3)$.

五数之和，六数之和也可以使用这样的思路进行求解。

代码

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        if(nums[i] >target and nums[i]>=0)  break;  //当nums[i]>target时，后面所有元素都大于target，直接break]

        if(i>0 and nums[i]==nums[i-1])      continue; //去重

        for(int j = i+1; j < nums.size(); j++){
            if (nums[i]+nums[j] > target and nums[i]+nums[j]>=0)  break; //当nums[i]+nums[j]>target时，后面所有元素都大于target，直接break

            if(j>i+1 and nums[j]==nums[j-1])      continue; //去重

            int left = j+1, right = nums.size()-1; //双指针

            while(left<right){ 
                
                if(nums[i]+nums[j]+nums[left]+nums[right]>target) right--;
                if(nums[i]+nums[j]+nums[left]+nums[right]<target) left++;

                else{
                    vector<int> temp = {nums[i], nums[j], nums[left], nums[right]};
                    result.push_back(temp);

                    while(left<right and nums[left]==nums[left+1]) left++;
                    while(left<right and nums[right]==nums[right-1]) right--;

                    left++;right--;
                }
            
            
            }
        }   
        
    } 

    return result;


}

9.总结

使用哈希法时，不同的数据结构一般有不同的使用场景，如下所示:

同时，哈希法处理重复元素是比较复杂，时间消耗较大。对于三数之和，四数之和等题目，使用排序，循环加上双指针法，并且注意去重处理是更好的处理方式。