Day 07

本文主要是介绍Day 07，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

454. 四数相加 II

分组+哈希

class Solution
{
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4){int num{};unordered_map<int, int> map;for (int i = 0; i < nums1.size(); i++){for (int j = 0; j < nums2.size(); j++){if (map.count(nums1[i] + nums2[j]) == 1){map[nums1[i] + nums2[j]]++;}else{map[nums1[i] + nums2[j]] = 1;}}}for (int i = 0; i < nums3.size(); i++){for (int j = 0; j < nums4.size(); j++){if (map.count(-(nums3[i] + nums4[j])) == 1){num += map[-(nums3[i] + nums4[j])];}}}return num;}
};

383. 赎金信

哈希映射

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

15. 三数之和 

双指针

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

18. 四数之和 

双指针

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

这篇关于Day 07的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---