代码随想录第7天 454 、 383 、15、18

代码随想录第7天

454. 四数相加 II

思路就是先统计nums1和num2各个元素之和出现的次数，然后遍历num3和nums4各个元素之和，看其相反数是否在map中，若在加上出现次数

class Solution {
public:
int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4) {
    unordered_map<int, int> map;
    for (auto &ele1 : nums1) {
        for (auto &ele2 : nums2) {
            map[ele1 + ele2]++;
        }
    }
    int res = 0;
    for (auto &ele1 : nums3) {
        for (auto &ele2 : nums4) {
            auto it = map.find(-(ele1 + ele2));
            if (it != map.end()) {
                res += it->second;
            }
        }
    }
    return res;
}
};

383. 赎金信

感觉和前面某题很类似，用map和数组都可以实现

class Solution {
public:

bool canConstruct(string ransomNote, string magazine) {
	vector<int> arr(26, 0);
    for (int i = 0; i < magazine.size(); i++) {
        arr[magazine[i] - 'a']++;
    }
    for (int i = 0; i < ransomNote.size(); i++) {
        arr[ransomNote[i] - 'a']--;
        if (arr[ransomNote[i] - 'a'] < 0) {
            return false;
        }
    }
    return true;
}
};


class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
	unordered_map<char, int> map;
	for (int i = 0; i < magazine.size(); i++) {
		map[magazine[i]]++;
	}
	for (int i = 0; i < ransomNote.size(); i++) {
		map[ransomNote[i]]--;
		if (map[ransomNote[i]] < 0) return false;
	}
	return true;
}
};

15. 三数之和

卡哥的视频讲得很清楚

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

18. 四数之和

在三数之和外面套一层for

需要注意的点是这里的target可以是负数所以在第一层剪枝除了要>target 还要>=0

其次会发现和越界[0,0,0,1000000000,1000000000,1000000000,1000000000]，1000000000 + 1000000000 + 1000000000就会越界所以我才用了long long类型为和，或者只加前面三个，判断target-nums[right]

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