一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1402|回复: 13
收起左侧

[算法题] 3Sum 和 4Sum

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-6-25 21:09:11 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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.                         if(!result.contains(temp))
  26.                         {
  27.                             result.add(temp);
  28.                         }
  29.                         
  30.                         k++;
  31.                         l--;
  32.                     }
  33.                     else if(sum < target)
  34.                     {
  35.                         k++;
  36.                     }
  37.                     else
  38.                     {
  39.                         l--;
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.         return result;
  45.         
  46.         
  47.     }
  48. }
复制代码
iFighting 发表于 2015-6-25 21:17:51 | 显示全部楼层
  1. if(!result.contains(temp))
  2.                         {
  3.                             result.add(temp);
  4.                         }
复制代码
这里!你用这个判断是否存在重复的是不靠谱的
回复 支持 1 反对 0

使用道具 举报

 楼主| love1point 发表于 2015-6-25 21:19:14 | 显示全部楼层
iFighting 发表于 2015-6-25 21:17
这里!你用这个判断是否存在重复的是不靠谱的

为啥呢,4sum能 ac的啊

非得加个HashSet来判断吗

谢啦
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 21:25:02 | 显示全部楼层
iFighting 发表于 2015-6-25 21:17
这里!你用这个判断是否存在重复的是不靠谱的

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

使用道具 举报

2015fallcser 发表于 2015-6-25 22:16:29 | 显示全部楼层
这两个题目并不一样,请仔细审题。3sum有duplicate, 4sum没有。
3sum里面你并没有判断冗余,必定超时了。需要在移动指针的时候判断一下是不是已经判断过这个值啦。
虽然大体上并没有改变他 O(n^2)的数量级,但是duplicate多到一定程度性能也是差蛮大的。
感觉这个用hash来做也挺不错,这样并不需要排序,而且可以很快知道有多少冗余。
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 22:24:34 | 显示全部楼层
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.
回复 支持 反对

使用道具 举报

2015fallcser 发表于 2015-6-25 22:29:24 | 显示全部楼层
love1point 发表于 2015-6-25 22:24
谢谢回复

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

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

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

使用道具 举报

 楼主| love1point 发表于 2015-6-25 22:30:31 | 显示全部楼层
2015fallcser 发表于 2015-6-25 22:29
哎呦不好意思看错了。。。
4sum没说他们都是unique的。。。视力不好看到unique看串了。。。之前没做过, ...

嗯,没事哈,多谢回复

我再研究研究
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 22:46:59 | 显示全部楼层
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. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 22:47:53 | 显示全部楼层
不管还是疑问,为啥 4 sum不用加上上面的判断呢
回复 支持 反对

使用道具 举报

 楼主| love1point 发表于 2015-6-25 22:48:03 | 显示全部楼层
2015fallcser 发表于 2015-6-25 22:29
哎呦不好意思看错了。。。
4sum没说他们都是unique的。。。视力不好看到unique看串了。。。之前没做过, ...

不管还是疑问,为啥 4 sum不用加上上面的判断呢
回复 支持 反对

使用道具 举报

kissy 发表于 2015-7-17 04:07:30 | 显示全部楼层
之前看到的答案,觉得写的挺好的:
3sum http://www.jiuzhang.com/solutions/3sum/
4sum http://www.jiuzhang.com/solutions/4sum/
回复 支持 反对

使用道具 举报

singku 发表于 2016-2-6 05:18:41 | 显示全部楼层
3sum 是排序的吗 题目没说有序啊
回复 支持 反对

使用道具 举报

cascade15 发表于 2016-2-17 07:16:22 | 显示全部楼层
不是,但是可以排序先
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 21:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表