3Sum 和 4Sum

3 sum: https://leetcode.com/problems/3sum/
4 sum:  https://leetcode.com/problems/4sum/

这两道题我觉得本质上是一样的，代码除了一个是三个数另外一个4个数以外，其他的唯一区别就是一个和为0，一个为 target，其他的代码都一样。为啥代码就改了一点点，为啥4 sum能过， 3 sum却提示 time limit exceeded 呢？ 求分析，还是疑惑中。


3 sum:

1. public class Solution {
   
2.     public List<List<Integer>> threeSum(int[] nums) {
   
3.         List<List<Integer>> result = new ArrayList();
   
4.         
   
5.         Arrays.sort(nums);
   
6.         for(int i = 0; i < nums.length; i++)
   
7.         {
   
8.             int j = i + 1;
   
9.             int k = nums.length - 1;
   
10.             while(j < k)
    
11.             {
    
12.                 int sum = nums[i] + nums[j] + nums[k];
    
13.                 if(sum == 0)
    
14.                 {
    
15.                     ArrayList<Integer> temp = new ArrayList<Integer>();
    
16.                     temp.add(nums[i]);
    
17.                     temp.add(nums[j]);
    
18.                     temp.add(nums[k]);
    
19.                     
    
20.                     if(!result.contains(temp))
    
21.                     {
    
22.                         result.add(temp);
    
23.                     }
    
24.                     
    
25.                     j++;
    
26.                     k--;
    
27.                 }   
    
28.                 else if(sum < 0)
    
29.                 {
    
30.                     j++;
    
31.                 }
    
32.                 else
    
33.                 {
    
34.                     k--;
    
35.                 }
    
36.             }
    
37.         }
    
38.         return result;
    
39.     }
    
40. }

复制代码

4 sum：

1. public class Solution {
   
2.     public List<List<Integer>> fourSum(int[] nums, int target) {
   
3.         List<List<Integer>> result = new ArrayList<List<Integer>>();
   
4.         
   
5.         Arrays.sort(nums);
   
6.         
   
7.         for(int i = 0; i < nums.length; i++)
   
8.         {
   
9.             for(int j = i + 1; j < nums.length; j++)
   
10.             {
    
11.                 int k = j + 1;
    
12.                 int l = nums.length - 1;
    
13.                 while(k < l)
    
14.                 {
    
15.                     int sum = nums[i] + nums[j] + nums[k] + nums[l];
    
16.                     if(sum == target)
    
17.                     {
    
18.                         List<Integer> temp = new ArrayList<Integer>();
    
19.                         temp.add(nums[i]);
    
20.                         temp.add(nums[j]);
    
21.                         temp.add(nums[k]);
    
22.                         temp.add(nums[l]);
    
23.                     
    
24. 
    
25.                     
    
26.                         if(!result.contains(temp))
    
27.                         {
    
28.                             result.add(temp);
    
29.                         }
    
30.                         
    
31.                         k++;
    
32.                         l--;
    
33.                     }
    
34.                     else if(sum < target)
    
35.                     {
    
36.                         k++;
    
37.                     }
    
38.                     else
    
39.                     {
    
40.                         l--;
    
41.                     }
    
42.                 }
    
43.             }
    
44.         }
    
45.         return result;
    
46.         
    
47.         
    
48.     }
    
49. }

复制代码

1. if(!result.contains(temp))
   
2.                         {
   
3.                             result.add(temp);
   
4.                         }

复制代码

这里！你用这个判断是否存在重复的是不靠谱的

2015fallcser 发表于 2015-6-25 22:29
哎呦不好意思看错了。。。
4sum没说他们都是unique的。。。视力不好看到unique看串了。。。之前没做过， ...

你说的对，

3 sum , 这种题目是需要判断相同的元素
比如 [-1, -1, 0, 1]
这两个-1 确实要判断一下
多谢提醒

加上判断就ac了

1. public class Solution {
   
2.     public List<List<Integer>> threeSum(int[] nums) {
   
3.         List<List<Integer>> result = new ArrayList();
   
4.         
   
5.         Arrays.sort(nums);
   
6.         for(int i = 0; i < nums.length; i++)
   
7.         {
   
8.             if(i != 0 && nums[i] == nums[i-1])
   
9.             {
   
10.                 continue;
    
11.             }
    
12.             int j = i + 1;
    
13.             int k = nums.length - 1;
    
14.             while(j < k)
    
15.             {
    
16.                 int sum = nums[i] + nums[j] + nums[k];
    
17.                 if(sum == 0)
    
18.                 {
    
19.                     ArrayList<Integer> temp = new ArrayList<Integer>();
    
20.                     temp.add(nums[i]);
    
21.                     temp.add(nums[j]);
    
22.                     temp.add(nums[k]);
    
23.                     
    
24.                     if(!result.contains(temp))
    
25.                     {
    
26.                         result.add(temp);
    
27.                     }
    
28.                     
    
29.                     j++;
    
30.                     k--;
    
31.                 }   
    
32.                 else if(sum < 0)
    
33.                 {
    
34.                     j++;
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                     k--;
    
39.                 }
    
40.             }
    
41.         }
    
42.         return result;
    
43.     }
    
44. }
    

复制代码

2015fallcser 发表于 2015-6-25 22:16
这两个题目并不一样，请仔细审题。3sum有duplicate, 4sum没有。
3sum里面你并没有判断冗余，必定超时了。 ...

谢谢回复

我仔细看了一下，两道题目没有说本身的元素是否有冗余啊

3 sum： 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:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.





4 sum: 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.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.

iFighting 发表于 2015-6-25 21:17
这里！你用这个判断是否存在重复的是不靠谱的

为啥呢，4sum能 ac的啊

非得加个HashSet来判断吗

谢啦

iFighting 发表于 2015-6-25 21:17
这里！你用这个判断是否存在重复的是不靠谱的

3 sum 提示 time limit exceeded, 是 时间复杂度的问题吧，即使不能用 if 来判断重复，改了这个if，时间复杂度还是没降下来啊

这两个题目并不一样，请仔细审题。3sum有duplicate, 4sum没有。
3sum里面你并没有判断冗余，必定超时了。需要在移动指针的时候判断一下是不是已经判断过这个值啦。
虽然大体上并没有改变他 O(n^2)的数量级，但是duplicate多到一定程度性能也是差蛮大的。
感觉这个用hash来做也挺不错，这样并不需要排序，而且可以很快知道有多少冗余。

love1point 发表于 2015-6-25 22:24
谢谢回复

我仔细看了一下，两道题目没有说本身的元素是否有冗余啊

哎呦不好意思看错了。。。
4sum没说他们都是unique的。。。视力不好看到unique看串了。。。之前没做过，没仔细看。应该是可能会有

3sum也是可能会有。这个ac过，有印象
没说一定有，没有没有，就是可能会有嘛，你的代码肯定要能处理这种情况啊。

2015fallcser 发表于 2015-6-25 22:29
哎呦不好意思看错了。。。
4sum没说他们都是unique的。。。视力不好看到unique看串了。。。之前没做过， ...

嗯，没事哈，多谢回复

我再研究研究

不管还是疑问，为啥 4 sum不用加上上面的判断呢