代码随想录算法训练营第7天| ● 454.四数相加II ● 383. 赎金信 ● 15. 三数之和 ● 18. 四数之和

454.两数相加 Ⅱ

mydemo--(超时失败)

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int count = 0;
        for(int i=0; i<nums1.size(); i++)
          for(int j=0; j<nums2.size(); j++)
            for(int k=0; k<nums3.size(); k++)
              for(int d=0; d<nums4.size(); d++)
                if(nums1[i]+nums2[j]+nums3[k]+nums4[d] == 0)      
                    count++;
        return count;  
    }
};

时间复杂度O(n^4)

mydemoV2--(卡哥思路)--(成功)

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    
        unordered_map<int,int> map;
        int count = 0;
        int target = 0;
        //auto iter;

        for(int i=0; i<nums1.size(); i++)
            for(int j=0; j<nums2.size(); j++)
            {
                auto iter = map.find(nums1[i]+nums2[j]);
                
                if(iter == map.end())//如果没找到
                    map.insert(pair<int,int>(nums1[i]+nums2[j], 1));
                else
                    iter->second ++;
            }
        
        for(int i=0; i<nums3.size(); i++)
            for(int j=0; j<nums4.size(); j++)
            {
                auto iter = map.find(target-nums3[i]-nums4[j]);
                if(iter != map.end())
                    count += iter->second;
            }
        
        return count;

    }
};

一个小坑：

auto iter = map.find(a) //没问题

auto iter;	//报错，auto类型必须一开始就初始化
iter = map.find(a); 

卡哥代码

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    
        unordered_map<int,int> map;
        int count = 0;
        int target = 0;
  
        for(int a : nums1){
            for(int b : nums2)
                map[a+b]++; //ps: map的value有默认初始值，为0
        }

        for(int c : nums3)
            for(int d : nums4){
                if(map.find(target-c-d) != map.end())
                count += map[target-c-d];
            }

        return count;
    }
};

383.赎金信

mydemo--(自己思路)--(成功)

一次就通过！

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        
        unordered_map<int, int> map;  
        for(char b : magazine)
            map[b]++;

        for(char a: ransomNote)
        {
            if(map[a]>0) map[a]--;
            else return false;
        }
        
        return true;
    }
};

时间复杂度O(n)

mydemoV2--（自己思路)--(失败)

用数组来做，大体应该没问题，但是逻辑细节上有问题

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        
        int lenA = ransomNote.size();
        int lenB = magazine.size();

        for(int i=0; i<lenA; i++)
        {
            for(int j=0; j<lenB; j++)
            {
                if(ransomNote[i]==magazine[j])
                {
                    for(; j<lenB-1; j++)
                        magazine[j] = magazine[j+1];
                    lenB--;
                    break;
                }
            }
            return false;
        }

        return true;
    }
};

时间复杂度O(n^3)

卡哥代码

依然是空间换时间的哈希表，但是这里数值不大，分布不散，所以卡哥选择了用数组而不是用map。

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};

        if(ransomNote.size()>magazine.size())
            return false;
        
        for(int i=0; i<magazine.length(); i++)
        {
            record[magazine[i]-'a'] ++;
        }

        for(int j=0; j<ransomNote.length(); j++)
        {
            record[ransomNote[j]-'a']--;
            if(record[ransomNote[j]-'a']<0)
                return false;
        }
        return true; 
    }
};

15.三数之和

mydemo--(卡哥思路)--(失败)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        sort(nums.begin(), nums.end());
        int len = nums.size();
        int target = 0;
        //unordered_set<int> result;
        unordered_set<unordered_set<int>> result;

        for(int i=0; i<len-2; i++)
        {
            int left=i+1, right=len-1; 
            while(left<right)
            {
                if(nums[i]+nums[left]+nums[right] > target)
                {
                    right--;
                    continue;
                }
                if(nums[i]+nums[left]+nums[right] < target)
                {
                    left++;
                    continue;
                }
                if(nums[i]+nums[left]+nums[right] == target)
                {
                    //if(result.find(vector<int,int,int>{nums[i], nums[left], nums[right]}) != result.end())
                    if( result.find(unordered_set<int>{nums[i], nums[left], nums[right]})  !=  result.end() )
                        result.insert(unordered_set<int>{nums[i], nums[left], nums[right]});
                }
            }
        }

        return vector(result);
    }
};

报错

                    if( result.find(unordered_set<int>{nums[i], nums[left], nums[right]})  !=  result.end() )
                        result.insert(unordered_set<int>{nums[i], nums[left], nums[right]});

这里有些语法问题，还不太会改。

mydemoV2--(卡哥思路)--(成功)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    int len = nums.size();

    //for(int i=0; i<len-2;i++) //我的demo，没报错
    for(int i=0; i<len; i++)	//卡哥demo
    {
        if(nums[i]>0) break;;
        //if(nums[i] == nums[i-1] && i>0) continue; //报错
        if(i>0 && nums[i] == nums[i-1]) continue;

        int left = i+1;
        int right = len-1;

        while(left < right)
        {
            if(nums[i]+nums[left]+nums[right] > 0)  right--;
            else if(nums[i]+nums[left]+nums[right] < 0)  left++;
            else{
                result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                
                //报错
                //while(nums[right] == nums[right-1]) right--;
                //while(nums[left] == nums[left+1])   left++;
                
                /*成功
                while(right>1 && nums[right] == nums[right-1]) right--;
                while(left<len-1 && nums[left] == nums[left+1])   left++;
                */
                /*成功
                while(nums[right] == nums[right-1] && left<right) right--;
                while(nums[left] == nums[left+1] && left<right)   left++;
                */
                while(left<right && nums[right] == nums[right-1]) right--;
                while(left<right && nums[left] == nums[left+1])   left++;
                right--;
                left++;
            }
        }
    }
    
    return result;
    }
};

报错：越下界

这种报错就是说，数组下标出现了负数(因为下标should be unsigned offest)

细节Ⅰ：

//if(nums[i] == nums[i-1] && i>0) continue; //报错
if(i>0 && nums[i] == nums[i-1]) continue;

这段报错是因为顺序写错了，要先判断 i>0 ，不然[i-1]可能会越下界

细节Ⅱ

//报错
//while(nums[right] == nums[right-1]) right--;
//while(nums[left] == nums[left+1])   left++;

这里会出现越下界错误，考虑一个特殊例子：

[0,0,0,0,0,0,0,0]

right会一路向北，当right==0时，[right-1]会越下界

细节Ⅲ

//for(int i=0; i<len-2;i++) //我的demo，没报错
for(int i=0; i<len; i++)	//卡哥demo

我的考虑是对的，因为题目说了len>=3，所以需要考虑 i 最多只能取到[len-3]

不过卡哥这里也是对的，因为:

when  i == len-2;
	left = len-1
    right = len-1
无法通过while(left < right)
i++
---又一轮新的循环---
when i == len-1;
	left = len > right = len-1
无法通过while(left < right)
---循环结束---

卡哥代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());

        for(int i=0; i<nums.size(); i++)
        {
            if(nums[i]>0)
                return  result;
        
            if(i>0 && nums[i] == nums[i-1])
                continue;
            
            int left = i+1;
            int right = nums.size()-1;
            while(left<right)
            {
                if(nums[i]+nums[left]+nums[right]>0)
                    right--;
                else if(nums[i]+nums[left]+nums[right]<0)
                    left++;
                else
                {
                    result.push_back(vector<int>{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++;
                }
            }
        } 
        return result;
    }
};

18.四数之和

mydemo--(卡哥思路)--(成功)

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        
        for(int k=0; k<len-3; k++)
        {
            if(nums[k]>target && nums[k]>=0)    break;
            //注意先判断k>0，防止越下界
            if(k>0 && nums[k]==nums[k-1])   continue;

            for(int i=k+1; i<len-2; i++)
            {
                //if(nums[k]+nums[i] > target && nums[i]>=0)  return result;;
                if(nums[k]+nums[i] > target && nums[i]>=0)  break;
                //if(i>(k+1) && nums[i] == nums[i+1]) i++;  
                //if(i>(k+1) && nums[i] == nums[i-1]) i++;
                if(i>(k+1) && nums[i] == nums[i-1]) continue;  

                int left = i+1;
                int right = len-1;
                while(left < right)
                {
                    if((long) nums[k]+nums[i]+nums[left]+nums[right] > target) right--;
                    else if((long) nums[k]+nums[i]+nums[left]+nums[right] < target) left++;
                    else{
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        while(left < right && nums[right]==nums[right-1])   right--;
                        while(left < right && nums[left]==nums[left+1])     left++;
                        right--;
                        left++;
                    }
                }
            }
        }

        return result;
    }
};

问题Ⅰ

//if(i>(k+1) && nums[i] == nums[i+1]) i++; 

这就是经典错误，只考虑到元组和元组不能重复，但没考虑到元组内部的元素可以重复

例子：

问题Ⅱ

//if(i>(k+1) && nums[i] == nums[i-1]) i++;

按照逻辑，不是i++，应当是 continue;

问题Ⅲ

for(int i=k+1; i<len-2; i++)
            {
                //if(nums[k]+nums[i] > target && nums[i]>=0)  return result;;
                if(nums[k]+nums[i] > target && nums[i]>=0)  break;

这里是第二层遍历，进行剪枝后就break到第一层遍历即可，如果是 return的话就会直接终止程序，会漏找元组。

问题四

if((long) nums[k]+nums[i]+nums[left]+nums[right] > target) right--;
else if((long) nums[k]+nums[i]+nums[left]+nums[right] < target) left++;

(long)为强制类型转换

(type) expression 

这里，力扣的数据里有一些会很大，相加可能会超出int的范围，所以转换成long进行操作。

卡哥代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

本栏目推荐文章
• 2024/1/13 算法笔记
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 算法练习题
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• 三数之和与四数之和 18
• [代码随想录] 第四天

之和 随想录 训练营 随想 算法随想录 之和 训练营 数组 之和 随想录 训练营 随想 随想录 之和 训练营 随想 之和 训练营 随想 代码 随想录 训练营 随想 算法 算法 随想录 训练营 随想 算法 随想录 训练营 序列 算法 随想录 训练营 数组 算法 随想录 训练营 总和 子集 算法 随想录 训练营