3Sum
题目例子思路代码 3Sum Closet
题目思路代码 4Sum
题目思路代码
3Sum
题目
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets.
例子
For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
思路
先排序，然后从头遍历i， 从i后第一个数和最后一个数开始向中间靠拢。跳过重复的数。
代码
class Solution {
public:
vector<vector<int>> threeSum(
vector<int>& nums) {
vector<vector<int>> resultVec;
sort(nums.begin(), nums.end());
int i =
0;
int j =
0;
int k =
0;
for (i=
0; i<nums.size(); i++) {
j = i+
1;
k = nums.size()-
1;
while (k > j) {
int sum1 = nums[j]+nums[k];
if (sum1 == -nums[i]) {
vector<int> tmpVec;
tmpVec.push_back(nums[i]);
tmpVec.push_back(nums[j]);
tmpVec.push_back(nums[k]);
resultVec.push_back(tmpVec);
while (j < k && nums[j]==tmpVec[
1]) j++;
while (j < k && nums[k]==tmpVec[
2]) k--;
}
else if (sum1 > -nums[i]) {
k --;
}
else {
j ++;
}
}
while (i+
1<nums.size()-
1 && nums[i+
1]==nums[i]) i++;
}
return resultVec;
}
};
3Sum Closet
题目
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
思路
先排序，然后从头遍历i， 从i后第一个数和最后一个数开始向中间靠拢，如果和小于target就j++，如果和大于target就k–。跳过重复的i。
代码
class Solution {
public:
int threeSumClosest(
vector<int>& nums,
int target) {
sort(nums.begin(), nums.end());
int mindiff = nums[
0]+nums[
1]+nums[
2];
for (
int i=
0; i<nums.size(); i++) {
int j = i+
1;
int k = nums.size()-
1;
while (j < k) {
if (nums[i]+nums[j]+nums[k]-target ==
0) {
return target;
}
else if (
abs(nums[i]+nums[j]+nums[k] - target) <
abs(mindiff - target)) {
mindiff = nums[i]+nums[j]+nums[k];
}
if (nums[i]+nums[j]+nums[k] > target) {
k--;
}
else {
j ++;
}
while (i<nums.size() && nums[i]==nums[i+
1]) {
i++;
}
}
}
return mindiff;
}
};
4Sum
题目
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0. A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
思路
同3Sum一样，遍历数组来确定前两个数，第三个和第四个从剩下的数组的头尾开始向中间靠拢。
代码
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++) {
for (
int j=i+
1; j<nums.size(); j++) {
int left = j+
1;
int right = nums.size()-
1;
int targetNum = target - nums[i] - nums[j];
while (left < right) {
vector<int> tmp;
if (nums[left] + nums[right] == targetNum) {
tmp.push_back(nums[i]);
tmp.push_back(nums[j]);
tmp.push_back(nums[left]);
tmp.push_back(nums[right]);
result.push_back(tmp);
left++;
right--;
while (left<right && nums[left-
1]==nums[left]) left++;
while (right>left && nums[right+
1]==nums[right]) right--;
}
else if (nums[left] + nums[right] < targetNum){
left++;
}
else {
right--;
}
}
while (nums[j]==nums[j+
1]) j++;
}
while (nums[i]==nums[i+
1]) i++;
}
return result;
}
};
