时间复杂度:O(N),空间复杂度:O(N)
第一想法:创建一个哈希表,存下nums[i] + nums[j],再遍历nums3和nums4得到nums[k]+nums[l],从哈希表中找0-nums[k] - nums[l]即可。
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
//创建哈希表建立索引,降低时间复杂度
unordered_map<int, int>hash;
int ret = 0;
for(auto& e : nums1)
for(auto& f : nums2)
hash[e+f]++;
//使用哈希表查找
for(auto& e : nums3)
for(auto& f : nums4)
{
if(hash[-e-f] > 0)
{
ret += hash[-e-f];
}
}
return ret;
}
};
时间复杂度:O(N),空间复杂度:O(S),S为小写字母数
第一想法:创建哈希表,把magazine中的字符和数量存起来,再遍历ransoNote,看看是否符合即可
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
//创建哈希表,创建索引
unordered_map<char, int> hash;
for(auto& e : magazine)
{
hash[e]++;
}
for(auto& e : ransomNote)
{
if(hash[e] > 0)
{
hash[e]--;
}
else
{
return false;
}
}
return true;
}
};
时间复杂度:O(N^2),空间复杂度:O(N)
第一想法:先排序,固定一个数,把它变成两数之和
困难:去重问题
看了题解:明白了如何去重,保证符合数组的条件情况下,判断它和前一个元素是否相同
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//排序+双指针
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
//枚举第一个数
int n = nums.size();
for(int i = 0; i < n-2; i++)
{
//第一个数大于0,直接返回
if(nums[i] > 0) break;
//第一个数
int x = nums[i];
//x和后面两个数相加,大于0 直接break
if(x + nums[i+1] + nums[i+2] > 0) break;
//当前x和最后两个数相加,小于0 枚举下一个第一个数
if(x + nums[n-1] + nums[n-2] < 0) continue;
//去重
if(i > 0 && i < n-2 && x == nums[i-1]) continue;
//枚举第二、三个数
int left = i+1, right = n-1;
while(left < right)
{
int s = x + nums[left] + nums[right];
if(s > 0) --right;
else if(s < 0) ++left;
else
{
ans.push_back({x, nums[left++], nums[right--]});
//去重
while(left < right && nums[left] == nums[left-1]) ++left;
while(right > left && nums[right] == nums[right+1]) --right;
}
}
}
return ans;
}
};
时间复杂度:O(N^3),空间复杂度:O(N)
第一想法:先排序,固定两个数,把它变成两数之和
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//排序+三指针
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
//枚举第一个数
int n = nums.size();
for(int i = 0; i < n-3;)
{
int x = nums[i];
//枚举第二个数
for(int j = i + 1; j < n-2; )
{
int y = nums[j];
//枚举第三四个数
int left = j+1, right = n-1;
while(left < right)
{
long s = x + y + (long)nums[left] + nums[right];
if(s > target) --right;
else if(s < target) ++left;
else
{
ans.push_back({x, y, nums[left++], nums[right--]});
//去重
while(left < right && nums[left] == nums[left-1]) ++left;
while(right > left && nums[right] == nums[right+1]) --right;
}
}
//去重
++j;
while(j < n-2 && nums[j] == nums[j-1]) ++j;
}
//去重
++i;
while(i < n-3 && nums[i] == nums[i-1]) ++i;
}
return ans;
}
};