四数相加II
- 时间复杂度 o(n2)
- 空间复杂度 o(n)
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> two_sum;
int total = 0;
for (int a : nums1) {
for(int b : nums2) {
two_sum[a + b]++;
}
}
// 在第二次遍历时不构造新的哈希表,不仅省去了空间的开销,又避免了再次比较的时间,很巧妙
for(int c : nums3) {
for(int d : nums4) {
if (two_sum.count(- c - d)) {
total += two_sum[- c - d];
}
}
}
return total;
}
};
赎金信
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int> destination;
for(char ch : ransomNote) {
destination[ch]++;
}
unordered_map<char, int> source;
for(char ch : magazine) {
source[ch]++;
}
for(auto pair : destination) {
if(source[pair.first] >= pair.second) {
continue;
} else {
return false;
}
}
return true;
}
};
三数之和
- 时间复杂度 o(n2)
- 空间复杂度 o(1)
原本使用哈希表来解答,但是在去重的时候,一些判断总是出问题,越改越麻烦,
tips: 在涉及到去重问题时,要想到用双指针
任意顺序返回的话,一般可以烤炉先排序
ps:做剪枝操作的时候,应该用nums[i] == nums[i-1]来判断,而不用nums[i] == nums[i+1]来判断,否则像,[-1,-1, 2]这种情况就被跳过了(即时使用当前值,而非延时使用)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int i = 0;
while(i < nums.size()) {
if(nums[i] > 0) return ans;
int left = i + 1, right = nums.size() - 1;
if(i > 0 && nums[i] == nums[i - 1]) {
i++;
continue;
}
while(left < right) {
if(nums[i] + nums[left] + nums[right] == 0) {
ans.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 (nums[i] + nums[left] + nums[right] < 0 && left < right) {
++left;
}
else if(left < right) {
--right;
}
}
i++;
}
return ans;
}
};
四数之和
- 时间复杂度 o(n3)
- 空间复杂度 o(1)
tips: 双指针法总是可以将时间复杂度降一个数量级
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ans{};
sort(nums.begin(), nums.end());
for(int first = 0; first < nums.size(); ++first) {
if(nums[first] > target && nums[first] > 0) break;
if(first && nums[first] == nums[first - 1]) continue;
for(int second = first + 1; second < nums.size(); ++second) {
if((long long)nums[first] + nums[second] > target && (long long)nums[first] + nums[second] > 0) break;
if(second > first + 1 && nums[second] == nums[second - 1]) continue;
int left = second + 1, right = nums.size() - 1;
while(left < right) {
if((long long)nums[first] + nums[second] + nums[left] + nums[right] == target) {
ans.push_back({nums[first], nums[second], 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((long long)nums[first] + nums[second] + nums[left] + nums[right] > target && left < right) {
--right;
} else if(left < right) {
++left;
}
}
}
}
return ans;
}
};
标签:四数,15,nums,++,随想录,second,right,first,left
From: https://www.cnblogs.com/cscpp/p/18192422