two sum
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> rec(2,-1);
unordered_map<int,int> m;
int n = nums.size();
if(n<2)
return rec;
for(int i=0;i<n;i++)
{
if(m.find(target-nums[i])==m.end())
m[nums[i]] = i;
else
{
rec[0] = m[target-nums[i]];
rec[1] = i;
}
}
return rec;
}
};
3 sum
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
int n = nums.size();
sort(nums.begin(),nums.end());
if(n<=2)
return result;
for(int i=0;i<n-2;i++)
{
int j = i+1;
int k = n-1;
while(j<k)
{
if(nums[i]+nums[j]+nums[k]==0)
{
vector<int> rec;
rec.push_back(nums[i]);
rec.push_back(nums[j]);
rec.push_back(nums[k]);
result.push_back(rec);
j++;
k--;
while(j<k&&nums[j-1]==nums[j])//注意，此处的j加过1了
j++;
while(j<k&&nums[k+1]==nums[k])//注意，此处的k减过1了
k--;
}
else if(nums[i]+nums[j]+nums[k]<0)
j++;
else
k--;
}
while(i<n-3&&nums[i+1]==nums[i])
i++;
}
return result;
}
};
3Sum Closest
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(),nums.end());
int last = -1;
int minClosest = INT_MAX;
for(int i=0;i<n;i++)
{
int j = i+1;
int k = n-1;
while(j<k)
{
int sum = nums[i]+nums[j]+nums[k];
if(sum<target)
j++;
else if(sum>target)
k--;
else if(sum==target)
{
j++;
k--;
}
if(abs(target-sum)<minClosest)
{
minClosest = abs(target-sum);
last = sum;
}
}
}
return last;
}
};
4 sum
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int n = nums.size();
if(n<=3)
return result;
sort(nums.begin(),nums.end());
for(int i=0;i<n-3;i++)
{
for(int j=i+1;j<n-2;j++)
{
int k = j+1;
int l = n-1;
int sum = target - nums[i] - nums[j];
while(k<l)
{
if(sum == nums[k] + nums[l])
{
vector<int> rec;
rec.push_back(nums[i]);
rec.push_back(nums[j]);
rec.push_back(nums[k]);
rec.push_back(nums[l]);
result.push_back(rec);
k++;
l--;
while(k<l&&nums[k-1]==nums[k])
k++;
while(k<l&&nums[l+1]==nums[l])
l--;
}
else if(nums[k] + nums[l] < sum)
{
k++;
}
else
{
l--;
}
}
while(j<n-2&&nums[j]==nums[j+1])
j++;
}
while(i<n-3&&nums[i]==nums[i+1])
i++;
}
return result;
}
};
利用set来实现：
3 sum
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
set<vector<int>> mSet;
int n = nums.size();
sort(nums.begin(),nums.end());
if(n<=2)
return result;
for(int i=0;i<n-2;i++)
{
int j = i+1;
int k = n-1;
while(j<k)
{
if(nums[i]+nums[j]+nums[k]==0)
{
vector<int> rec;
rec.push_back(nums[i]);
rec.push_back(nums[j]);
rec.push_back(nums[k]);
mSet.insert(rec);
j++;
k--;
}
else if(nums[i]+nums[j]+nums[k]<0)
j++;
else
k--;
}
}
return vector<vector<int>>(mSet.begin(),mSet.end()); //注意此种写法！！！
}
};
4 sum
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int n = nums.size();
if(n<=3)
return result;
set<vector<int>> mSet;
sort(nums.begin(),nums.end());
for(int i=0;i<n-3;i++)
{
for(int j=i+1;j<n-2;j++)
{
int k = j+1;
int l = n-1;
int sum = target - nums[i] - nums[j];
while(k<l)
{
if(sum == nums[k] + nums[l])
{
vector<int> rec;
rec.push_back(nums[i]);
rec.push_back(nums[j]);
rec.push_back(nums[k]);
rec.push_back(nums[l]);
mSet.insert(rec);
k++;
l--;
}
else if(nums[k] + nums[l] < sum)
{
k++;
}
else
{
l--;
}
}
}
}
return vector<vector<int>>(mSet.begin(),mSet.end());//注意此种写法！！！
}
};
