刷题第六天

代码随想录刷题第六天 | 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

454.四数相加II

这个题分完组之后和两数其实差不多 得重新复习STL了，好多东西全忘了，

class Solution {public:    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {        unordered_mapumap;        for(int a:nums1){            for(int b:nums2){                umap[a+b]++;            }        }        int count = 0;        for(int c:nums3){            for(int d:nums4){                if(umap.find(0-(c+d))!=umap.end()){                    count = count + umap[0-(c+d)];                }            }        }        return count;    }};

383. 赎金信

这个题倒是很简单，和之前那个题目一样，创个数组就行，就26个字母

class Solution {puindex.php/tags-41973.html" >blic:    bool canConstruct(string ransomNote, string magazine) {        int nums[27] = {0};        for(int i = 0;i  
18. 四数之和
 
这里可以有负数，所以剪枝操作有问题，不能和三数之和一样，然后居然还会溢出，完全没注意，好多细节
 
class Solution {public:    vector fourSum(vector& nums, int target) {        vector result;        sort(nums.begin(), nums.end());        for (int k = 0; k  target && nums[k] >= 0) {            break;             }            if (k > 0 && nums[k] == nums[k - 1]) {                continue;            }            for (int i = k + 1; i  target && nums[k] + nums[i] >= 0) {                    break;                }                if (i > k + 1 && nums[i] == nums[i - 1]) {                    continue;                }                int left = i + 1;                int right = nums.size() - 1;                while (right > left) {                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {                        right--;                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]   left && nums[right] == nums[right - 1]) right--;                        while (right > left && nums[left] == nums[left + 1]) left++;                        right--;                        left++;                    }                }            }        }        return result;    }};
                                                （）（）