454. 四数相加II【中等】
emmmm,猪脑子解法(特指我自己)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { int result = 0; for(int i = 0; i < nums1.size(); i++) { for(int j = 0; j < nums1.size(); j++) { for(int k = 0; k < nums1.size(); k++) { for(int l = 0; l < nums1.size(); l++) if(nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) result++; } } } return result; }
};
|
果不其然,超时了!
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map<int, int> sumCount; int result = 0;
for (int a : nums1) { for (int b : nums2) { sumCount[a + b]++; } }
for (int c : nums3) { for (int d : nums4) { result += sumCount[-(c + d)]; } }
return result; } };
|
使用哈希表来存储 nums1
和 nums2
所有可能的和,然后再遍历 nums3
和 nums4
来查找相应的负和。这样可以将时间复杂度降低到 $O(n^2)$。
383. 赎金信【简单】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| class Solution { public: bool canConstruct(string ransomNote, string magazine) { unordered_map<char, int> ransomNoteMap;
for (char a : ransomNote) { ransomNoteMap[a]++; }
for (char b : magazine) { if (ransomNoteMap[b] > 0) { ransomNoteMap[b]--; } }
for (char a : ransomNote) { if (ransomNoteMap[a] > 0) { return false; } }
return true; } };
|
15. 三数之和【中等】
我的思路:
- 使用 set 对结果进行去重
- 先对数组进行排序以便于去重操作
- 然后进行三重循环暴力解决以查找符合要求的结果
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) { set<vector<int>>resultSet; sort(nums.begin(), nums.end()); for(int i = 0; i < nums.size(); i++) { for(int j = i + 1; j < nums.size(); j++) { for (int k = j + 1; k < nums.size(); k++) { if(nums[i] + nums[j] + nums[k] == 0) { vector<int> ijk; ijk.push_back(nums[i]); ijk.push_back(nums[j]); ijk.push_back(nums[k]); resultSet.insert(ijk); } } } } vector<vector<int>> result(resultSet.begin(), resultSet.end()); return result; }
};
|
很不幸,超时了……
双指针法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include <vector> #include <algorithm>
class Solution { public: std::vector<std::vector<int>> threeSum(std::vector<int>& nums) { std::vector<std::vector<int>> result; std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) { 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) { result.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--; } else if (sum < 0) { left++; } else { right--; } } } return result; } };
|
解决思路
排序:
- 首先对数组进行排序。排序后,能够方便地使用双指针法,并且可以轻松跳过重复的元素。
外层循环:
- 使用一个循环遍历数组的每个元素,将当前元素视为三元组的第一个元素 ( a )。
- 为了避免重复,检查当前元素是否与前一个元素相同。如果相同,则跳过。
双指针法:
- 初始化两个指针:
left
指向当前元素的下一个位置,right
指向数组的最后一个元素。
- 使用这两个指针来寻找另外两个元素 ( b ) 和 ( c ),使得 ( a + b + c = 0 )。
计算和:
- 在
left
小于 right
的情况下,计算三元组的和:
- 如果和为零,找到一个有效的三元组,将其存入结果中,并移动指针,同时跳过重复的元素。
- 如果和小于零,说明需要增大和,因此移动
left
指针向右。
- 如果和大于零,说明需要减小和,因此移动
right
指针向左。
避免重复:
- 在找到有效三元组后,使用循环跳过所有相同的
left
和 right
元素,确保结果中的三元组是唯一的。
返回结果:
整体流程
- 时间复杂度:排序的时间复杂度为 ( O(n \log n) ),而双指针遍历的时间复杂度为 ( O(n^2) )。因此整体的时间复杂度为 ( O(n^2) )。
- 空间复杂度:主要使用了额外的空间来存储结果,空间复杂度为 ( O(k) ),其中 ( k ) 是找到的三元组的数量。
18. 四数之和【中等】
思路与上面那题一致
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| 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 (i > 0 && nums[i] == nums[i - 1]) continue; for (int j = i + 1; j < nums.size(); j++) { 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 = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right]; if (sum < target) { left++; } else if (sum > target) { right--; } else { result.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 result; } };
|