昨天看了一下别的东西,导致昨天没有练习打卡,今天补上昨天的学习知识。

454.四数相加II

建议:本题是 使用map 巧妙解决的问题,好好体会一下 哈希法 如何提高程序执行效率,降低时间复杂度,当然使用哈希法 会提高空间复杂度,但一般来说我们都是舍空间 换时间, 工业开发也是这样。

题目链接:力扣

思路:给了我们四个数组,在四个数组之中分别找出一个元素,得到的结果为0,并且不用进行去重操作。可以先是遍历前面两个数组A+B,然后遍历后面的两个数组C+D。如果要是四个元素相加等于0,则可以得到结果元素。考虑到数组的下标比较大,考虑map和set,不仅要统计是否出现过,还要统计出现的次数,因此这里我们使用map解决这道题目。

map key:a+b value:3

这里的0-(c+d)=a+b则选择出来了。思路清晰了,则比较简单了。

为什么要分成两份,遍历前面两个的过程为n^2,然后后面也为n^2。如果要是分为1,3类型,则为n与n^3的情况。

这里使用undered_map对重复数据不敏感,并且效率高。见下面的测试代码

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {

        //首先,声明一个map,里面放置很多自己想要的数据,map的key就是相应的a+b的数值,value是a+b出现的次数
        unordered_map<int,int> mymap;

        for(int a:nums1)
        {
            for(int b:nums2)
            {
                mymap[a+b]++;//相当是value值想加
            }
        }

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

                }
                
            }
        }
        return count;



    }
};

383. 赎金信  

建议:本题和 242.有效的字母异位词是一个思路 ,算是拓展题.

题目链接:力扣

下面的这个代码是自己写的,比较容易理解.

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<ransomNote.size();i++)
        {
            record[ransomNote[i]-'a']++;
        } 

        for(int i=0;i<magazine.size();i++)
        {
            record[magazine[i]-'a']--;
        } 

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

        return true;


    }
};

15. 三数之和 

建议:本题虽然和 两数之和 很像,也能用哈希法,但用哈希法会很麻烦,双指针法才是正解,可以先看视频理解一下 双指针法的思路,文章中讲解的,没问题 哈希法很麻烦。

题目链接:力扣

这个地方相较于两个的情况复杂一点点,a+b+c=0;这一个题要进行去重,因此是不能够使用hash法,首先进行排序,就是可以使用双指针方式进行求解.代码随想录算法训练营15期 Day 7 | 454.四数相加II 、 383. 赎金信 、15. 三数之和 、18. 四数之和-LMLPHP

这里的关键是要进行去重,因为结果集里面是不能够存在重复的东西. 

步骤:①首先进行排序,然后遍历,如果大于0,直接进行一个return;
②去重操作,判断num[i]==num[i+1]与num[i]==num[i-1]的情况.注意结果集里面可以存在重复,因此遍历的时候使用num[i]==num[i-1]进行一个continue操作.
③注意left<right,不能够是=的情况.
④判断条件是否成立,成立的情况下,收割结果.
⑤防止{-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,1}的情况出现.

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 (right > left) {
               
                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. 四数之和  ----没看懂,后面再看

建议: 要比较一下,本题和 454.四数相加II 的区别,为什么 454.四数相加II 会简单很多,这个想明白了,对本题理解就深刻了。 本题 思路整体和 三数之和一样的,都是双指针,但写的时候 有很多小细节,需要注意,建议先看视频。

题目链接:力扣

思路:在上面的那个题的基础上,增加了一个循环条件而已.四个数想加等于target的过程,存在一些细节(剪枝和去重操作)

06-01 02:45