454、四数相加Ⅱ

·map哈希表

---

当初不知四数相加的好，做完四数之和发现~oh 这题真简单

题目链接：https://leetcode.cn/problems/4sum-ii/

前提：计算四个数组中多少个元组满足条件（值可以重复）

思路：四个数组分别两两相加|时间复杂度O(n^2)
   前两个数组相加的值作为map的键
   map中查找等于（0-后两个数组相加的值）的键
   找到则+该键值（这个值可能大于一）

代码实现：unordered_map哈希表
     时间复杂度O(n^2)
     空间复杂度O(n)

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> umap;
        int count=0;
        for(int i1:nums1){
            for(int i2:nums2){
                umap[i1+i2]++;
            }
        }
        for(int i3:nums3){
            for(int i4:nums4){
                if(umap.find(0-(i3+i4))!=umap.end())count=count+umap[0-(i3+i4)];
            }
        }
        return count;
    }
};

收获摘要：map哈希法O(n ^2)比暴力O(n ^4)要快

学习的文章链接：https://programmercarl.com/0454.四数相加II.html

383、赎金信

·数组哈希表

---

为了写一封完整的信，咔咔剪杂志doge

题目链接：https://leetcode.cn/problems/ransom-note/

前提：nums1中每个字符只能使用一次
   数组中只有小写字母

思路：使用长度为26的数组//对应26个小写字母
   遍历nums1，对应数组++
   遍历nums2，对应数组--
   数组中有数<0则false

代码实现：数组哈希表
     时间复杂度O(n)
     空间复杂度O(1)

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int num[26]={0};
        for(char i:magazine){
            num[i-'a']++;
        }
        for(char i:ransomNote){
            num[i-'a']--;
        }
        for(int j:num){
            if(j<0)return false;
        }
        return true;
    }
};

收获摘要：剪杂志很解压doge
     <0返回false，因为杂志没有对应的字母！
     遍历前可以添加下列代码来减少计算：

if (ransomNote.size() > magazine.size()) {
            return false;
        }

学习的文章链接：https://programmercarl.com/0383.赎金信.html

15、三数之和

·双指针yyds

---

重难点：去重

题目链接：https://leetcode.cn/problems/3sum/

前提：一个整数数组，值不重复的三元组
   3<=nums.length<=3000

思路：首先进行数组排序，方便比较和去重
   i遍历数组+双指针法
   先排除i>0的情况 //减少运算
   再不看i=i-1 //去重
   i，i+1和nums.size()-1三个指针所指数值之和sum与0相比：
      大于零尾巴指针向前移，小于零头部指针向后移。
      等于零存入结果并对下一步进行去重

代码实现：双指针法
     时间复杂度O(n^2)(小于？)
     空间复杂度O(n)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());
        int left,right,sum;
        for(int i=0;i<nums.size()-2;i++){
            if(nums[i]>0)return result;
            if(i>0&&nums[i]==nums[i-1])continue;
            left=i+1;
            right=nums.size()-1;
            while(left<right){
                sum=nums[i]+nums[left]+nums[right];
                if(sum==0){
                    result.push_back(vector<int>{nums[i],nums[left],nums[right]});
                    left++;//找到一个三元组后，收缩
                    right--;
                    while(left<right&&nums[left]==nums[left-1])left++;
                    while(left<right&&nums[right]==nums[right+1])right--;//left<right，防止下标越界
                }
                else{
                    if(sum>0)right--;
                    if(sum<0)left++;
                }
            }

        }
        return result;
    }
};

收获摘要：去重要考虑边界和一些特殊情况，双指针咔咔剪枝doge

学习的文章链接：https://programmercarl.com/0015.三数之和.html#哈希解法

18、四数之和

·双指针法plus

---

套娃，三数之和又套了一层

题目链接：https://leetcode.cn/problems/4sum/submissions/

前提：一个整数数组，值不重复的四元组
   -10^9 <= target <= 10^9
   1 <= nums.length <=200

思路：在三数之和的思路基础上，再套一层循环

代码实现：双指针plus
     时间复杂度O(n^3)
     空间复杂度O(n)

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int i,j,left,right;
        long sum;
        sort(nums.begin(),nums.end());
        for(i=0;i<nums.size()-3;i++){
            if(nums.size()<4)return result;//数组过短，直接返回result
            if(nums[i]>target&&target>=0)return result;
            if(i>0&&nums[i]==nums[i-1])continue;
            for(j=i+1;j<nums.size()-2;j++){
                if(j>i+1&&nums[j]==nums[j-1])continue;//外面多了一层i，所以j>i+1保证j=i+1已经遍历过了
                left=j+1;
                right=nums.size()-1;
                while(left<right){
                    sum=(long)nums[i]+(long)nums[j]+(long)nums[left]+(long)nums[right];//啊,这...int相加超范围了
                    if(sum==target){
                        result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        left++;
                        right--;
                        while(left<right&&nums[left]==nums[left-1])left++;
                        while(left<right&&nums[right]==nums[right+1])right--;
                    }
                    else{
                        if(sum>target)right--;
                        if(sum<target)left++;
                    }
                }
            }
        }
        return result;
    }
};

收获摘要：剪枝操作要注意数值范围！在升序排序后，target<0和target>0的情况不同，不要把需要的值也剪了。
     去重多考虑数值变化和边界。
     注意int范围，相加可能溢出！

学习的文章链接：https://programmercarl.com/0018.四数之和.html#其他语言版本

学习的视频链接：https://www.bilibili.com/video/BV1DS4y147US/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6

---

学习时长：4h40min