454.四数相加II

LeetCode题目

注意事项

• 注意set和map的初始化（本题自动为0）

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int, int> map;
        int n = nums1.size();
        int output = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = nums1[i] + nums2[j];
                auto iter = map.find(temp);
                if (iter != map.end())
                    map[temp]++;
                else map[temp] = 1; 
            }    
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int temp = nums3[i] + nums4[j];
                auto iter = map.find(-temp);
                if (iter != map.end())
                    output += iter->second;
            }    
        }
        return output;
    }
};

383. 赎金信

LeetCode题目

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int data[26] = {0};
        for (int i = 0; i < magazine.length(); i++)
            data[magazine[i] - 'a']++;
        for (int i = 0; i < ransomNote.length(); i++) {
            data[ransomNote[i] - 'a']--;
            if (data[ransomNote[i] - 'a'] < 0)
                return false;
        }
        return true;
    }
};

15. 三数之和

LeetCode题目

注意事项

• 注意双指针的用法
• 时间比较吃紧

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        int len = nums.size();
        int numsmax = nums[len - 1];
        for (int pointer1 = 0; pointer1 <= len - 3; pointer1++) {
            if (nums[pointer1] > 0)
                break;
            if (pointer1 > 0 && nums[pointer1] == nums[pointer1 - 1])
                continue;
            int pointer2 = pointer1 + 1, pointer3 = len - 1;

            while (-nums[pointer1] - nums[pointer2] > numsmax) {
                pointer2++;
                if (pointer2 >= len - 1)
                    break;
            }

            while (pointer2 < pointer3) {
                if ((nums[pointer1] + nums[pointer2] + nums[pointer3]) > 0)
                    pointer3--;
                else if ((nums[pointer1] + nums[pointer2] + nums[pointer3]) < 0)
                    pointer2++;
                else {
                    result.push_back({nums[pointer1], nums[pointer2], nums[pointer3]});
                    pointer3--;
                    pointer2++;
                    while (pointer2 < pointer3 && nums[pointer2] == nums[pointer2 - 1])
                        pointer2++;
                    while (pointer2 < pointer3 && nums[pointer3] == nums[pointer3 + 1])
                        pointer3--;
                    
                }
            }
        }
        return result;
    } 
};