代码随想录算法训练营day7(day8补) | 454.四数相加II 383.赎金信 15.三数之和 18.四数之和

刷题笔记day7

454.四数相加II

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

没有好思路。

自己写的代码

看了题解后写的代码：

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int sumAB, sumCD;
        unordered_map<int, int> umap;
        for (auto A : nums1) {
            for (auto B : nums2) {
                sumAB = A + B;
                ++umap[sumAB];
            }
        }
        int counts = 0;
        for (auto C : nums3) {
            for (auto D : nums4) {
                sumCD = C + D;
                if (umap.find(0 - sumCD) != umap.end()) {
                    counts += umap[0 - sumCD];
                }
            }
        }
        return counts;
    }
};

看了题解后的收获

四数之和是否为0可以用两两组合的方式去验证。

383.赎金信

文章讲解：代码随想录
是否自己做出来通过全部用例：

遇到的困难/犯的错误

思路：先把magazine中的字符和出现的次数存入键值对umap，然后遍历ransomNote，使用umap.find(c)去查找字符，找到就让次数-1。如果次数=0或没找到就是false。

自己写的代码

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> umap;
        for (auto c1 : magazine) {
            ++umap[c1];
        }
        for (auto c2 : ransomNote) {
            auto iter = umap.find(c2);
            if (iter != umap.end()) {
                if (iter->second == 0) {
                    return false;
                }
                else {
                    --iter->second;  
                }
                
            }
            else {
                return false;
            }
        }
        return true;
    }
};

看了题解后的收获

用数组更简单省时间。

15.三数之和

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

用的map做，效率很低，好在实现了，虽然只击败了5%。T T

自己写的代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        map<vector<int>, int> map;
        vector<vector<int>> result;
        for (int i = 0; i < nums.size() - 2; ++i) {
            int left = i + 1;
            int right = nums.size() - 1;
            while (1) {
                if (nums[i] + nums[left] + nums[right] != 0) {
                    if (nums[i] + nums[left] + nums[right] < 0) {
                        ++left;
                    }
                    else {
                        --right;
                    }
                    if (left == right) {
                        break;
                    }
                }
                else {
                    if (map.find({nums[i], nums[left], nums[right]}) != map.end()) {
                        ++left;
                        --right;
                        if (right <= left) {
                            break;
                        }
                        continue;
                    }
                    map[{nums[i], nums[left], nums[right]}]; 
                    map[{nums[i], nums[right], nums[left]}];
                    map[{nums[right], nums[i], nums[left]}];
                    map[{nums[right], nums[left], nums[i]}];
                    map[{nums[left], nums[right], nums[i]}];
                    map[{nums[left], nums[i], nums[right]}];
                    result.push_back({nums[i], nums[left], nums[right]});
                    --right;
                    ++left;
                    if (right <= left) {
                        break;
                    }
                    continue;
                }
            }
        }
        return result;
    }
};

看了题解后的收获

用两层for循环，学习去重操作的思想，如果nums[i]和nums[i-1]相等。

18.四数之和

文章讲解：代码随想录
是否自己做出来通过全部用例：否

遇到的困难/犯的错误

按照三数和的思路，照搬，多嵌套一层循环。细节没处理好。

自己写的代码

自己写之后忽略了一些细节，一直通不过，照着题解写的：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] > target && nums[i] >= 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
                    break;
                }
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) {
                        --right;
                    }
                    else if ((long)nums[i] + nums[j] + nums[left] + nums[right] < target) {
                        ++left;
                    }
                    else {
                        result.push_back({nums[i], nums[j], 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;
    }
};

看了题解后的收获

不管是三、四，甚至五、六数之和，都是这个逻辑，无非就是多嵌套几层循环，时间复杂度多*n。
注意细节：i > 0, j > i + 1。从每一层的第二个数开始去重。