454.四数相加II
题目链接：https://leetcode.cn/problems/4sum-ii/submissions/
算法核心：转化为去哈希表中查找元素的思路。
思路：
直观的想法是使用四层暴力循环，但是时间复杂度太高。可以想到，其实可以把它转化为元素查找的思路。
两两一组，1 2两个数组元素之和存入哈希表中，然后遍历3+4的时候，计算0减去3+4元素的和，记为target，去哈希表中查改元素是否存在。
代码：
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> search;
int len1=nums1.size();
int len2 = nums2.size();
int len3 = nums3.size();
int len4 = nums4.size();
int count = 0;
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
int sum = nums1[i] + nums2[j];
if(search.find(sum) == search.end())
{
search[sum] = 1;
}
else
{
search[sum] += 1;
}
}
}
for(int i=0;i<len1;i++)
{
for(int j=0;j<len2;j++)
{
int sum = nums3[i] + nums4[j];
int target = 0 - sum;
if(search.find(target) != search.end())
{
int target_count = search[target];
count += target_count;
}
}
}
return count;
}
};
- 赎金信
题目：https://leetcode.cn/problems/ransom-note/
核心思路：查找一个元素是否在某个集合中。
将magazine的元素存入map，并计数，在map中查找ransomNote的元素，如果全部查到，返回true，否则false
代码：
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<int, int> magazine_map;
int lenm = magazine.length();
int lenr = ransomNote.length();
for(int i=0;i<lenm;i++)
{
if(magazine_map.find(magazine[i]) == magazine_map.end())
{
magazine_map[magazine[i]] = 0;
}
magazine_map[magazine[i]] += 1;
}
for(int i=0;i<lenr;i++)
{
if(magazine_map.find(ransomNote[i]) != magazine_map.end() && magazine_map[ransomNote[i]]!=0)
{
magazine_map[ransomNote[i]] -= 1;
}
else
return false;
}
return true;
}
};
- 三数之和
题目链接：https://leetcode.cn/problems/3sum/submissions/
算法核心：这里涉及到去重的操作，用哈希表比较复杂。结果要求去重，可以想到需要对数组进行排序。
思路：
i从头遍历，left指向剩下元素的左边，right指向剩下元素的右边，排序过后的数据，和的变化是有规律的，和大于0，right--，和小于0，left++。
重要的是两个指针去重的过程。
代码：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//用三个指针解决
vector<vector<int>> result;
sort(nums.begin(), nums.end());
int len = nums.size();
for(int i=0;i<len-2;i++)
{
if(i>0&&nums[i]==nums[i-1])
continue;
int left = i+1;
int right = len-1;
while(left<right)
{
if((nums[i] + nums[left] + nums[right]) < 0)
{
left++;
}
else if((nums[i] + nums[left] + nums[right]) >0)
{
right--;
}
else
{
result.push_back(vector<int> {nums[i], nums[left],nums[right]});
left++;
right--;
while(left<right && left!=(i+1) &&nums[left]==nums[left-1])
left++;
while(left<right && right!=(len-1)&&nums[right]==nums[right+1])
right--;
}
}
}
return result;
}
};
第18题. 四数之和
题目链接：https://leetcode.cn/problems/4sum/submissions/
算法思想：同三数之和
注意和越界问题（暂未解决）
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int len = nums.size();
vector<vector<int> > result;
for(int i=0;i<len-3;i++)
{
if(i>0&&nums[i]==nums[i-1])
continue;
if(target>=0 && nums[i]>target)
break;
for(int j=i+1;j<len-2;j++)
{
if(j>i+1&&nums[j]==nums[j-1])
continue;
if (nums[j] + nums[i] > target && nums[j] + nums[i] >= 0) {
break;
}
int left = j+1;
int right = len-1;
while(left<right)
{
cout<<"i:"<<i<<" j"<<j <<"start: left:"<<left<<" right:"<<right<<endl;
if(nums[i] + nums[j] + nums[left] + nums[right] > target)
{
right--;
}
else if(nums[i] + nums[j] + nums[left] + nums[right] < target)
{
left++;
}
else{
result.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
left++;
right--;
// cout<<"left:"<<left<<" right:"<<right<<endl;
while(left<right &&nums[left]==nums[left-1])
left++;
while(left<right &&nums[right]==nums[right+1])
right--;
// cout<<"end: left:"<<left<<" right:"<<right<<endl;
}
}
}
}
return result;
}
};
