1).2sum
1.题意：找出数组中和为target的所有数对
2.思路：排序数组，然后用两个指针i、j，一前一后，计算两个指针所指内容的和与target的关系，如果小于target，i右移，如果大于,j左移，否则为其中一个解
3.时间复杂度：O(nlgn)+O(n)
4.空间：O(1)
5.代码：
void twoSum(vector<int>& nums,int numsSize,int target,vector<vector<int>>& twoSumRes) {
int i=0,j=numsSize-;
while(i<j){
if(nums[i]+nums[j] < target ){
i++;
}else if(nums[i]+nums[j] > target ){
j--;
}else{
vector<int> oneOfRes;
oneOfRes.push_back(nums[i]);
oneOfRes.push_back(nums[j]);
twoSumRes.push_back(oneOfRes);
i++;
/* 找不重复的数对 */
while(nums[i]==nums[i-])i++;
j--;
/* 找不重复的数对 */
while(nums[j]==nums[j+])j--;
}
}
}2).3sum
1.题意：找出数组中和为target的所有三个数的组合，任意两个组合中的元素不能全相同，例如，target=5，2,2,1和1,2,2就是重复的组合，因为两个组合中的元素完全相同，只能取其中的一个。
2.思路：这个题可以转换题意，取数组中的一个元素a，求剩余元素中和为target-a的所有不重复数对，转换为2Sum问题。
3.时间复杂度：O(nlgn)+O(n*n)
4.空间：O(1)
5.代码：
class Solution {
public:
void twoSum(vector<int>& nums,int numsSize,int start,int target,vector<vector<int>>& twoSumRes) {
int i=start,j=numsSize-;
while(i<j){
if(nums[i]+nums[j] < target ){
i++;
}else if(nums[i]+nums[j] > target ){
j--;
}else{
vector<int> oneOfRes;
oneOfRes.push_back(nums[i]);
oneOfRes.push_back(nums[j]);
twoSumRes.push_back(oneOfRes);
i++;
while(nums[i]==nums[i-])i++;
j--;
while(nums[j]==nums[j+])j--;
}
}
}
vector<vector<int>> threeSum(vector<int>& nums) {
size_t nums_size = nums.size();
vector<vector<int>> res;
sort(nums.begin(),nums.end());
for(size_t i=;i<nums_size;i++){
if(i> && (nums[i]==nums[i-])){
continue;
}
vector<vector<int>> twoSumRes ;
twoSum(nums,nums_size,i+,-nums[i],twoSumRes);
if(!twoSumRes.empty()){
size_t j_times = twoSumRes.size();
for(size_t j=;j<j_times;j++){
twoSumRes[j].insert(twoSumRes[j].begin(),nums[i]);
res.push_back(twoSumRes[j]);
}
}
}
return res;
}
};3).4Sum,kSum
1.题目：求所有和为target的4个元素的不重复组合，任意两个组合中的元素不能全相同。
2.思路：递归，4Sum->3Sum->2Sum
3.时间复杂度：O(nlgn)+O(n*n*...*n),k-1个n
代码：
class Solution {
public:
vector<vector<int>> towSum(vector<int>& nums,int numsSize,int start,int target)
{
vector<vector<int>> res;
int i = start,j=numsSize-;
while(i<j){
if(nums[i] + nums[j] < target){
i++;
}else if(nums[i] + nums[j] > target){
j--;
}else{
vector<int> item;
item.push_back(nums[i]);
item.push_back(nums[j]);
res.push_back(item);
i++;
while(nums[i]==nums[i-])i++;
j--;
while(nums[j]==nums[j+])j--;
}
}
return res;
}
vector<vector<int>> kSum(vector<int>& nums,int numsSize,int start,int k,int target)
{
if(k==){
return towSum(nums, numsSize, start, target);
}else{
vector<vector<int>> kSumRes;
for(size_t i=start;i<numsSize;i++){
if(i>start && (nums[i]==nums[i-])){
continue;
}
vector<vector<int>> item = kSum(nums,numsSize,i+,k-,target-nums[i]);
size_t itemSize = item.size();
for(size_t j=;j<itemSize;j++){
item[j].insert(item[j].begin(),nums[i]);
kSumRes.push_back(item[j]);
}
}
return kSumRes;
}
}
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
size_t numsSize = nums.size();
return kSum(nums,numsSize,,,target);
}
};4).类似的题，3Sum Closest
1.题目：
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).2.时间：O(nlgn)+O(n*m*2),m*2表示试探次数
3.代码
class Solution {
public:
bool twoSum(vector<int>& nums,int numsSize,int start,int target)
{
int i=start,j=numsSize-;
while(i<j){
if(nums[i] + nums[j] < target){
i++;
}else if(nums[i] + nums[j] > target){
j--;
}else{
return true;
}
}
return false;
}
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
size_t numsSize = nums.size();
int increasment = ;
while(true){
bool hasTwoSum = false;
for(size_t i=;i<nums.size();i++){
hasTwoSum = twoSum(nums,numsSize,i+,target+increasment-nums[i]);
if(hasTwoSum){
break;
}
hasTwoSum = twoSum(nums,numsSize,i+,target-increasment-nums[i]);
if(hasTwoSum){
increasment = -increasment;
break;
}
}
if(hasTwoSum){
break;
}
increasment++;
}
return target+increasment;
}
};5).后序：
这类题的算法原型就是2Sum,在求不重复的数对时，有个小技巧(排好序的基础上)，就是在求得arry[i]+arry[j] == target时，要去掉与arry[i]和arry[j]相等的元素。
这种使用两个指针处理数组的方法也很常见，例如，排序颜色数组，奇数偶数分类，有序数组中连续子数组和为target的所有组合等等