3sum 时间复杂度问题

3sum这个题目中，如果用hashset来判断，不知道为什么就会出现tle，我感觉两种方法的时间没有本质差别啊，请大家解答下，重点是在找到了3个数以后那一部分。
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result=new ArrayList<List<Integer>>();
//   Set<List<Integer>> set=new HashSet<List<Integer>>()
    int i=0,j=i+1,k=nums.length-1;
    Arrays.sort(nums);
    for(i=0;i<nums.length-2&&nums[i]<=0;i++)
    { j=i+1;k=nums.length-1;
       if(i==0||(i>0&&nums[i]!=nums[i-1]))
       {while(j<k)
        {
            if(nums[i]+nums[j]+nums[k]==0)
            {List<Integer> res=new ArrayList<Integer>();
                res.add(nums[i]);
                res.add(nums[j]);
                res.add(nums[k]);
                result.add(res);
                while(j<k&&nums[j]==nums[j+1])j++;
                while(j<k&&nums[k]==nums[k-1])k--;
                j++;k--;
            }
            else if(nums[i]+nums[j]+nums[k]>0)
            {
            k--;
            }
            else {
            j++;
            }
        }
       }
    }
    return result;
    }
}

这个事ac通过了的，判处重复的方法是通过跳过已经判断过的j,k；
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result=new ArrayList<List<Integer>>();
    Set<List<Integer>> set=new HashSet<List<Integer>>();
    int i=0,j=i+1,k=nums.length-1;
    Arrays.sort(nums);
    for(i=0;i<nums.length-2;i++)
    { j=i+1;k=nums.length-1;
        while(j<=nums.length-2&&j<k)
        {List<Integer> res=new ArrayList<Integer>();
            if(nums[i]+nums[j]+nums[k]==0)
            {
                res.add(nums[i]);
                res.add(nums[j]);
                res.add(nums[k]);
                if(set.add(res)
                {result.add(res);
                }
                j++;
                k--;
            }
            else if(nums[i]+nums[j]+nums[k]>0)
            k--;
            else
            j++;
        }
    }
    return result;
    }
}

这个是使用了hashset来判断重复，不知道对不对，我记得hashset.add是O(1)的时间复杂度啊，为什么会超过了time呢？？？

不知道正不正常，感觉现在做难度3的题很多想了好久都没一个完整的思路，都是些碎片，最后得看了别人的思路才行，内心十分纠结，但是不看又写不出来。。。好痛苦，希望能逐渐的学会别人的精华，做到自己写出来

caffery24 发表于 2015-7-8 21:44
意思是有很多重复的情况，都全部判断了一遍吗？所以超时了

应该是这样。比如[1 1 1 1 1 1 1 1 2 -3] 这个例子。本来找到第一个[1 2 -3]时，后面的1都可以直接跳过了。而第二段代码中还是坚持不懈地查询了后面的所有[1 2 -3]组合。两个代码最差时间复杂度一样，但是当有大量重复的时候，第一段代码事实上就接近O(N)了，而后者在任何情况下都是雷打不动的O(N^2)。而且第二段代码还创建了大量的不必要的ArrayList(即res)。我不知道垃圾回收的时间算不算在OJ的计时里，但是不管怎么说，这种本来不必要的创建-删除循环肯定会拖慢程序的效率。

caffery24 发表于 2015-7-8 13:29
第二个确实我是tle了啊，不知道是因为什么，刚才看了discuss有人也是用hashset超时了

两份代码我都读了，感觉第一种更好。不过两份都有没找到bug，在lintcode上试了试也都ac了。
你是在leetcode上超时吗？预期复杂度应该是O(n^2)

zhuli19901106 发表于 2015-7-8 13:13
而且第二份代码连括号都没匹配。。改了改以后，第二份代码也可以ac
两者的效率几乎没有差别，一个2071ms ...

第二个确实我是tle了啊，不知道是因为什么，刚才看了discuss有人也是用hashset超时了

楼主加个代码缩进吧，都四层括号了，可读性实在太低。
你可以通过改写代码减少括号层数。
另外，用括起来，这样能保留格式

zhuli19901106 发表于 2015-7-8 12:56
楼主加个代码缩进吧，都四层括号了，可读性实在太低。
你可以通过改写代码减少括号层数。
另外，用括起来 ...

嗯嗯，谢谢啊。。。这个是刚才实在想不通改烦了，也没注意格式，

caffery24 发表于 2015-7-8 13:01
嗯嗯，谢谢啊。。。这个是刚才实在想不通改烦了，也没注意格式，

而且第二份代码连括号都没匹配。。改了改以后，第二份代码也可以ac
两者的效率几乎没有差别，一个2071ms，一个2085ms

我记得我很久以前用hash好像也跪了，也是觉得奇怪，不知道是不是hash的overhead导致超时了。

试了试，leetcode还真超时了，莫非leetcode上的时间给的短点？那超时也就不奇怪了，常系数优化吧。反正算法的正确性应该是没问题。

记得当年做一道POJ的题目，2000ms的限制，我搞出过一个1999ms的ac，嘿嘿~~
实际上用些常数优化的方法，就能把时间降下去的。

呃，我发现我的旧code为啥超时了，因为我的算法错了囧。。。
我用的set去重元素，但元素可以重复用，改成map就过了。楼主这个set和我用法不一样，结果应该正确，但是这个做法不能剪枝，所以超时吧。