3sum 不sort怎么做？

我的代码如下但是对于1, 0, -1, 1 这个case res里面同时有 (1, 0, -1) 和 (0, -1, 1)， 并没有做到去重，
而且还需要处理  0, 0,0 的case
有没有人有好的想法？

1. class Solution {
   
2.     public List<List<Integer>> threeSum(int[] nums) {
   
3.         List<List<Integer>> res = new ArrayList<>();
   
4.         Set<Integer> seen = new HashSet<>();
   
5.         for(int i = 0; i <= nums.length - 3; i++){
   
6.              if(seen.contains(nums[i])) continue;
   
7.              int target = 0 - nums[i];
   
8.              twosum(nums, i+1, nums.length - 1, target, nums[i], res);
   
9.              seen.add(nums[i]);
   
10.         }
    
11.         
    
12.         return res;
    
13.     }
    
14.    
    
15.      public void twosum(int[] nums, int start, int end, int target, int first, List<List<Integer>> res){
    
16.         Set<Integer> set = new HashSet<>();
    
17.         for(int i = start; i <= end; i++){
    
18.            int find = target - nums[i];
    
19.            if(set.contains(find)){
    
20.                  res.add(Arrays.asList(first, nums[i], find));
    
21.            }
    
22.           set.add(nums[i]);
    
23.        }
    
24.      }
    
25. }

复制代码

为什么你不想sort? 不sort的话brute force，对每一个元素做 two sum就好了。

1. class Solution {
   
2.     // 不用排序的版本，超时
   
3.     public List<List<Integer>> threeSum(int[] nums) {
   
4.         List<List<Integer>> results = new ArrayList<>();
   
5. 
   
6.         Set<List<Integer>> set = new HashSet<>();
   
7.         Map<Integer, Integer> map = new HashMap<>();
   
8.         for (int num : nums) {
   
9.             map.put(num, map.getOrDefault(num, 0) + 1);
   
10.         }
    
11. 
    
12.         for (int i = 0; i < nums.length; i++) {
    
13.             // 注意 j 从 0 开始，因为内部还是需要判断升降序来去重，如果从 i + 1 开始可能会漏解
    
14.             for (int j = 0; j < nums.length; j++) {
    
15.                 int a = nums[i];
    
16.                 int b = nums[j];
    
17.                 int c = 0 - a - b;
    
18.                 // 去重
    
19.                 if (!(a >= b && b >= c)) {
    
20.                     continue;
    
21.                 }
    
22. 
    
23.                 if (map.containsKey(c)) {
    
24.                     map.put(a, map.get(a) - 1);
    
25.                     map.put(b, map.get(b) - 1);
    
26.                     map.put(c, map.get(c) - 1);
    
27.                 } else {
    
28.                     continue;
    
29.                 }
    
30. 
    
31.                 if (map.get(a) >= 0 && map.get(b) >= 0 && map.get(c) >= 0) {
    
32.                     // 去重
    
33.                     set.add(Arrays.asList(a, b, c));
    
34.                 }
    
35. 
    
36.                 map.put(a, map.get(a) + 1);
    
37.                 map.put(b, map.get(b) + 1);
    
38.                 map.put(c, map.get(c) + 1);
    
39.             }
    
40.         }
    
41. 
    
42.         results.addAll(set);
    
43.         return results;
    
44.     }
    
45. }

复制代码

1. class Solution {
   
2.     // 不用排序的版本，超时
   
3.     public List<List<Integer>> threeSum(int[] nums) {
   
4.         List<List<Integer>> results = new ArrayList<>();
   
5.         Set<List<Integer>> set = new HashSet<>();
   
6. 
   
7.         for (int i = 0; i < nums.length; i++) {
   
8.             for (int j = 0; j < nums.length; j++) {
   
9.                 int a = nums[i];
   
10.                 int b = nums[j];
    
11.                 int c = 0 - a - b;
    
12.                 if (!(a >= b && b >= c)) {
    
13.                     continue;
    
14.                 }
    
15.                 for (int k = 0; k < nums.length; k++) {
    
16.                     if (nums[k] == c && i != j && j != k && i != k) {
    
17.                         set.add(Arrays.asList(a, b, c));
    
18.                     }
    
19.                 }
    
20.             }
    
21.         }
    
22. 
    
23.         results.addAll(set);
    
24.         return results;
    
25.     }
    
26. }

复制代码

不排序两个版本均TLE， 前者过了倒数第二个case，最后一个3000个0的case 看脸跑，1200ms-1300ms之间，后者最后两个Case都TLE

sizem 发表于 2018-2-2 13:38
求解 什麼是去重？

avoid duplicates in the result

我上礼拜想的时候是
2sum存hashmap的时候把两个值一起存起来，但是这样空间复杂度会高一些
不知道能不能更优
或者直接set存结果集？

mimesis 发表于 2017-11-7 05:21
我上礼拜想的时候是
2sum存hashmap的时候把两个值一起存起来，但是这样空间复杂度会高一些
不知道能不能 ...

对于1, 0, -1, 1这个case 你的解法是怎么work的呀

slightlyOff 发表于 2017-11-7 06:24
对于1, 0, -1, 1这个case 你的解法是怎么work的呀

哦对。。我忘记了。。不能排序的话第一个外循环的数也没办法排重。。如果要排的话好像只能变成存3个数的hashmap那其实就是set去重结果集了
存3个数的时候比个大小从小到大存吧。。弱渣我想不到别的了orz

mimesis 发表于 2017-11-7 09:22
哦对。。我忘记了。。不能排序的话第一个外循环的数也没办法排重。。如果要排的话好像只能变成存3个数的h ...

这个题我面试的时候被问到了，我说三个数从小到大排，然后存。面试官说我还是sort，不符合要求。于是这轮面试就挂了。

不sort的话主要难点在于去除重复的答案，分两方面：

(1) Identity-去重
也就是说如果记录了一次(1, 0, -1)这样的结果，那么下一次出现(1, 0, -1)时，我们应该有一个数据结构可以判断这个结果是重复的

(2) Permutation-去重
也就是避免同时记录(1, 0, -1)和(-1, 1, 0)这样本质上相同的结果，去重方法是在枚举组合时，保持某种偏序关系——比如说三个数从小到大

我写了一份代码，可以用于提交LeetCode的3SUM：https://leetcode.com/problems/3sum/description/
不过这种不sort的代码速度挺慢的就是...

1. #include <cstdint>
   
2. #include <iostream>
   
3. #include <unordered_map>
   
4. #include <unordered_set>
   
5. #include <vector>
   
6. 
   
7. class Solution {
   
8. public:
   
9.   std::vector<std::vector<int>> threeSum(const std::vector<int> &nums) {
   
10.     // 统计每个数字的个数
    
11.     std::unordered_map<int, int> counts;
    
12.     for (const int value : nums) {
    
13.       ++counts[value];
    
14.     }
    
15. 
    
16.     std::vector<std::vector<int>> results;
    
17.     std::unordered_set<std::uint64_t> existence;
    
18. 
    
19.     for (const int l : nums) {
    
20.       for (const int r : nums) {
    
21.         // 设三个数为l, m, r
    
22.         // 为了"Permutation-去重"，只需要保留l <= m <= r的结果
    
23.         const int m = -(l + r);
    
24.         if (l > m || m > r) {
    
25.           continue;
    
26.         }
    
27. 
    
28.         // 用于加速计算的pre-check: m存在
    
29.         auto &mc = counts[m];
    
30.         if (mc <= 0) {
    
31.           continue;
    
32.         }
    
33. 
    
34.         // 拼接l, r以进行"Identity-去重"
    
35.         // 这里为了方便用了uint64_t，也可以用std::pair<int, int>之类的，但需要写一个
    
36.         // hash functor以提供给std::unordered_set，稍微麻烦一点
    
37.         std::uint64_t code = (static_cast<std::uint64_t>(l) << 32) | r;
    
38.         if (existence.find(code) != existence.end()) {
    
39.           continue;
    
40.         }
    
41. 
    
42.         // l, m, r可能是两个或三个相同的数字，我们需要检查counts里对应的数字有那么多个
    
43.         auto &lc = counts[l];
    
44.         auto &rc = counts[r];
    
45.         --lc; --mc; --rc;
    
46. 
    
47.         if (lc >= 0 && mc >= 0 && rc >= 0) {
    
48.           results.emplace_back(std::vector<int>({l, m, r}));
    
49.           existence.emplace(code);
    
50.         }
    
51. 
    
52.         ++lc; ++mc; ++rc;
    
53.       }
    
54.     }
    
55. 
    
56.     return results;
    
57.   }
    
58. };

复制代码

时间n方 空间n吧？

magicsets 发表于 2017-12-21 13:07
不sort的话主要难点在于去除重复的答案，分两方面：

(1) Identity-去重

其实你既然用hash table统计了，hash table的key就是所有的不同的num了，所以如果你的l , r 从hash table的key里来取值，你的O(n^2)就变成distinct的number的平方的，你的identity去重就可以不需要了

jason123 发表于 2018-2-2 07:56
其实你既然用hash table统计了，hash table的key就是所有的不同的num了，所以如果你的l , r 从hash table ...

求解 什麼是去重？