Leetcode第15题如果要求不能先把array排序

Leetcode 第15题， 给一个无序数组，求所有三个元素加起来等于0的集合，先给正常解法

1. public List<List<Integer>> threeSum(int[] nums) {
   
2.         Arrays.sort(nums);
   
3.         List<List<Integer>> res = new ArrayList<>();
   
4.         
   
5.         for(int i = 0; i < nums.length - 2; i++) {
   
6.             if(i > 0 && nums[i] == nums[i - 1]) continue;
   
7.             int sum = 0 - nums[i];
   
8.             int low = i + 1;
   
9.             int high = nums.length - 1;
   
10.             while(low < high) {
    
11.                 if(nums[low] + nums[high] == sum) {
    
12.                     res.add(Arrays.asList(nums[i], nums[low], nums[high]));
    
13.                     while(low < high && nums[low + 1] == nums[low]) low++;
    
14.                     while(low < high && nums[high - 1] == nums[high]) high--;
    
15.                     low++;
    
16.                     high--;
    
17.                 } else if(nums[low] + nums[high] < sum) {
    
18.                     low++;
    
19.                 } else {
    
20.                     high--;
    
21.                 }
    
22.             }
    
23.         }
    
24.         
    
25.         return res;
    
26.     }

复制代码

然后被问到如果不允许使用arrays.sort。。。该怎么解，我真的大大的脑袋。。。搜了很多答案都没有找到符合要求的，求高手提示一下啊啊啊， 加米加米

确实可以不用排序，而且排序也确实非必须，对比下2sum不需排序就达到了O(N)，而3sum必须排序才能达到O(N^2)就不符合了逻辑。
3sum的排序意义是，把不排序的两个O(N^2 + N^2)的操作变成O(NlogN + N^2)
不排序的算法很简单，就如一楼说的HashMap，去重有多种方法基础算法也不难。
简单来说 1. Map<Integer, List<int[]>> map = new HashMap<>();保存<2sum, List<int[]{index0,index1}>>
再设一个 Set<String> set查重
2. 两个loop算2sum和对应i,j加入map, 可以inner loop 从i+1算起，这样就保证i<j只用算一半
        for(int i = 0; i < len; i++)
            for(int j = i + 1; j < len; j++)
3. 然后新开for(int k = 0; k< n; k++)找到if(map.containsKey(-nums[k]))
取出list里每个int[], 如果k和i或j相等说明一个数用了第二次肯定不对，就continue // index查重
i,j,k不等的话分别取出nums[i],nums[j],nums[k]
4. 查重方式有很多，简单的比如三个数排序，然后加逗号间隔变成String放set里查重 "-3,1,2" //value查重
set已经有的话就continue，没有的话String加入set保存,三个数就是正确结果放到resultList


这样的时间复杂度也是O(N^2)，但就如一开始说的两个操作是O(N^2 + N^2)所以会比排序O(NlogN + N^2)要慢

首先，two sum是leetcode第一题，是最简单的题，简化了很多corn case，比如保证没有重复，只有一组解，而且由于只是2sum，所以hashmap的做法只是个特例。正常的做法就是先sort后双指针。如果是3sum，你还能试着在two sum用用hashmap，自己利用set去重，那么 对于4sum，5sum。Ksum， 这么做就很费劲了，也没有任何优势。而对于Ksum，排序后递归到2sum是正常做法。

感觉可以选一个点，再对其他的用HashMap求2sum？不过难点在于去重吧。

不知道小帅 发表于 2020-7-14 15:51
感觉可以选一个点，再对其他的用HashMap求2sum？不过难点在于去重吧。

先放set里去重呢？然后在2 sum

他说不许用array sort， 你自己写一个sort func 不可以吗

Wu_kong 发表于 2020-7-15 01:56
他说不许用array sort， 你自己写一个sort func 不可以吗

我感觉他的意思是好像如果不让排序的话？

比twosum就是多了最外圈一层loop，转为two sum变种即可？ 难点确实是去重，可以采用anagrams，对一组三个数字排序【1，2，-3】---> [-3,1,2] 然后把这个list加入set中.

conghao2016 发表于 2020-7-15 14:24
比twosum就是多了最外圈一层loop，转为two sum变种即可？ 难点确实是去重，可以采用anagrams，对一组三个数 ...

没错，2sum并不依赖于sort。

个人观点 排序的一个好处就就是不用考虑/容易去重 本身并没有在时间复杂度上帮助到算法

BobbyBear 发表于 2020-7-15 21:39
没错，2sum并不依赖于sort。

缘分啊 一起刷题不