3Sum 等类似题目分析

3Sum

题目描述：给定一个整数数组，找出其中的三个数之和为0的所有组合(排除相同的组合)。

分析：利用TwoSum 中两指针的思路，我们可以先将数组排序。要找到3个数之和为0，我们可以先固定一个数num[i],将i+1和len-1分别作为头指针和尾指针，当num[i]、num[i+1]与num[len-1]的和大于0时，移动尾指针；小于0时，移动头指针；等于0则找到一组数。在循环查找下一组解时，当下一个值与当前值相等会出现重复的解，此时可以跳过当前循环来去除重复。具体代码如下：

 1  vector<vector<int>> threeSum(vector<int>& nums) {
 2         sort(nums.begin(), nums.end());
 3     int len= nums.size();
 4     vector<vector<int> > res;
 5     vector<int> mid;
 6     for(int i=0;i<len-2;i++)
 7     {
 8         if (nums[i]>0) return res;
 9                 //防止出现重复
10         if (i> 0 && nums[i] == nums[i - 1]) continue;
11         int start= i+1, end = len-1;
12         while (start<end)
13         {
14             if ((nums[start] + nums[end] +nums[i])<0) start++;
15             else if ((nums[start] + nums[end] +nums[i])>0) end--;
16             else
17             {
18                 mid.push_back(nums[i]);
19                 mid.push_back(nums[start++]);
20                 mid.push_back(nums[end--]);
21                 res.push_back(mid);
22                 mid.clear();
23                                //防止出现重复
24                 while (start<end&&nums[start] == nums[start-1]) start++;
25                 while (start<end&&nums[end] == nums[end+1]) end--;
26             }
27         }
28     }
29     return res;
30     }

3Sum Closest

给定一个数组，找到三个数之和与目标值最相近，返回这个和。例如给定数组S = {-1 2 1 -4}, and target = 1.最近似目标值的是2 (-1 + 2 + 1 = 2)。

该题解法与上一题相似，每次循环要记录下sum值与目标值的差，并保存该sum值，如果sum值与目标值相等则直接返回。代码如下：

 1 int threeSumClosest(vector<int>& nums, int target) {
 2         sort(nums.begin(), nums.end());
 3     int len= nums.size();
 4     int res=0,result=0;
 5     int dist=INT_MAX;
 6     for(int i=0;i<len-2;i++)
 7     {
 8         if (i> 0 && nums[i] == nums[i - 1]) continue;
 9         int start= i+1, end = len-1;
10         while (start<end)
11         {
12             res=nums[start] + nums[end] +nums[i];
13             if (res<target)
14             {
15                 if(target-res<dist)
16                 {
17                     result=res;
18                     dist=target-res;
19                 }
20                 start++;
21                 while (start<end&&nums[start] == nums[start-1]) start++;
22             }
23             else if (res>target)
24             {
25                if(res-target<dist)
26                {
27                    result=res;
28                    dist=res-target;
29                }
30                end--;
31                while(start<end&&nums[end] == nums[end+1]) end--;
32             }
33             else 
34             return res;
35         }
36     }
37     return result;    
38  }

4Sum

找到数组中的四个数a,b,c,d,使得a+b+c+d=target。这与3Sum相同，只不过我们要先固定两个数，因此多了一个循环；为了比较方便，我们记sum=target-a-b,将sum与a+b比较，代码如下：

 1 vector<vector<int>> fourSum(vector<int>& nums, int target) {
 2         sort(nums.begin(), nums.end());
 3     int len= nums.size();
 4     vector<vector<int> > res;
 5     vector<int> mid;
 6     for(int i=0;i<len-3;i++)
 7     {
 8        if (i> 0 && nums[i] == nums[i - 1]) continue;
 9        for(int j=i+1;j<len-2;j++)
10        {
11            if (j>i+1 && nums[j] == nums[j - 1]) continue;
12            int start= j+1, end = len-1,sum=target-nums[i]-nums[j];
13            while(start<end)
14            {
15             if ((nums[start] + nums[end])<sum) start++;
16             else if ((nums[start] + nums[end])>sum) end--;
17             else
18             {
19                 mid.push_back(nums[i]);
20                 mid.push_back(nums[j]);
21                 mid.push_back(nums[start++]);
22                 mid.push_back(nums[end--]);
23                 res.push_back(mid);
24                 mid.clear();
25                 while (start<end&&nums[start] == nums[start-1]) start++;
26                 while (start<end&&nums[end] == nums[end+1]) end--;
27             }
28            }
29        }
30     }
31     return res;
32     }