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

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

时间：2023-09-13 16:36:46浏览次数：43  
标签：vector 四数 15 nums int 随想录 -- right left

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;
    }
};

标签：vector,四数,15,nums,int,随想录,--,right,left
From： https://www.cnblogs.com/lycnight/p/17700011.html

相关文章

  • 5999元-13999元买哪款？iPhone 15全系四款机型配置/价格对比
    苹果已经在凌晨正式发布了四款iPhone。分别是iPhone15、iPhone15 Plus、iPhone15Pro 和iPhone15ProMax，命名上没有一丝变化。先看价格，首先明确这次苹果起步价没涨，依然是5999元起。iPhone15：128GB5999元、256GB6999元、512GB8999元。iPhone15Plus：128GB6999元、2......
  • 【题解】[POI2015] MOD
    传送门挺恶心的感觉这题代码，就来写写题解。题目分析假设我们现在要删掉\((x,y)\)这条边，思考这样能贡献的最大或最小直径。不难发现，此时一棵树分裂成了两棵树\(a,b\)，我们令它们的直径分别为\(la,lb\)。将两棵树内直径的任意端点连起来，发现\(maxi=la+lb+1\)。将两棵树内直......
  • 15.3K Star，超好用的开源协作式数字白板：tldraw
    大家好，我是TJ今天给大家推荐一个开源协作式数字白板：tldraw。tldraw的编辑器、用户界面和其他底层库都是开源的，你可以在它的开源仓库中找到它们。它们也在NPM上分发，提供开发者使用。您可以使用tlDraw为您的产品创建一个临时白板，或者将其作为构建自己应用的工具来使用。在线体验......
  • DC-DC升压变换器直流隔离升压模块电源5v12v24v48v转60v80v110v150v220v250v300v500v80
    特点 效率高达80%以上 1*2英寸标准封装 单电压输出 价格低 稳压输出 工作温度:-40℃~+85℃ 阻燃封装，满足UL94-V0要求 温度特性好 可直接焊在PCB上应用HRBW2~40W系列模块电源是一种DC-DC升压变换器。该模块电源的输入电压分为：4.5~9V、9~18V、及18~36V、36~72VDC标准（2......
  • [代码随想录]Day43-动态规划part11
    题目：123.买卖股票的最佳时机III思路：达到dp[i][1]状态，有两个具体操作：操作一：第i天买入股票了，那么dp[i][1]=dp[i-1][0]-prices[i]操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1]=dp[i-1][1]那么dp[i][1]究竟选dp[i-1][0]-prices[i]，还是dp[i-1][1]呢？......
  • 还没发布就来了？iPhone 15系列机型价格配置图曝光
    明天凌晨1点，iPhone15系列就将正式发布，不过在发布前夕，有网友根据此前的各种爆料，制作了一张有关新iPhone的各型号价格和配置的图片，虽然这并不是官方公布的图片，但是也或多或少包含了人们对于新iPhone的期待。从网传图片可以发现，此次iPhone15系列将带来iPhone15、iPhone15Plus......
  • 代码随想录算法训练营第六天
    代码随想录算法训练营第六天|LeetCode454(四数相加II)LeetCode383(赎金信)LeetCode15(三数之和)LeetCode18(四数之和)454：四数相加IILeetCode454(四数相加II)思路：首先定义一个map，key放a和b两数之和，value放a和b两数之和出现的次数。遍历nums1和nums2数组，统计两个数......
  • 一图看懂iPhone 15系列：15/Plus/Pro/Pro Max有啥区别？详细配置对比
    距离iPhone15系列发布只剩下2天（北京时间9月13日凌晨1点），即将推出预计分别是iPhone15、iPhone15Plus，以及Pro系列的iPhone15Pro以及iPhone15ProMax。TrendForce集邦汇总了四款新机规格预测。硬件方面，受欧盟订定法案的限制，苹果也将于今年加入Type-C的行列，全新更换C口。iPho......
  • [代码随想录]Day42-动态规划part10
    题目：121.买卖股票的最佳时机思路：贪心做起来更简单；dp多此一举……状态0是有买入，状态1是代码：funcmaxProfit(prices[]int)int{lens:=len(prices)iflens==0{return0}dp:=make([][]int,lens)fori:=0;i<lens;i++{......
  • 代码随想录算法训练营第五天
    代码随想录算法训练营第五天|LeetCode242(有效的字母异位词)LeetCode349(两个数组的交集)LeetCode202(快乐数)LeetCode1(两数之和)242:有效的字母异位词LeetCode242(有效的字母异位词)classSolution{publicbooleanisAnagram(Strings,Stringt){......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99