3sum 不sort怎么做？

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

avoid duplicates in the result

我的想法是这样
遍历数组 对于每个数nums[i] 第二个数nums[j] 必须选大于等于nums[i]且i!=j, 第三个数nums[k]必须比nums[j]大与等于且j!=k, k!=i
这样就不会有重合的 不过time complexity是n三次 空间constant

for loop里面用2sum好像也挺方便的 时间n方 空间要求高 且考虑重复的时候可能会用到sort.

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

bunnyNova 发表于 2017-12-21 11:04
这个题我面试的时候被问到了，我说三个数从小到大排，然后存。面试官说我还是sort，不符合要求。于是这轮 ...

刚想到的，存答案的时候可以存两个数，因为是3 sum，存两个数就可以推断出第三个数，存的两个数分别存三个数中的最大值和最小值，这样就可以避免sort了。不过这个面试官到底想考察什么？？

黓龙君 发表于 2017-11-7 08:35
为什么你不想sort? 不sort的话brute force，对每一个元素做 two sum就好了。

不sort可以作为这个题的followup

沒 sort 且不超時 (單依然很慢)

1. class Solution {
   
2. public:
   
3.     vector<vector<int>> threeSum(vector<int>& nums) {
   
4.         unordered_map<int,bool> num1s;
   
5.         int zeroCnt=0;
   
6.         for(const int num:nums){
   
7.             if(!num)zeroCnt++;
   
8.             auto it=num1s.find(num);
   
9.             if(it==num1s.end())num1s.emplace_hint(it,num,false);
   
10.             else it->second=true;
    
11.         }
    
12.         vector<vector<int>> results;
    
13.         for(int i=0;i<nums.size()-2;i++){
    
14.             auto it1=num1s.find(nums[i]);
    
15.             if(it1==num1s.end()) continue;
    
16.             unordered_set<int> num2s(num1s.bucket_count(),num1s.hash_function(),num1s.key_eq());
    
17.             for(int j=i+1;j<nums.size()-1;j++){
    
18.                 if(nums[i]==0&&nums[j]==0) continue;
    
19.                 if(num1s.find(nums[j])==num1s.end()) continue;
    
20.                 auto it2=num2s.find(nums[j]);
    
21.                 if(it2!=num2s.end()) continue;
    
22.                 auto it3=num1s.find(-nums[i]-nums[j]);
    
23.                 if(it3!=num1s.end()){
    
24.                     if((-nums[i]-nums[j]!=nums[i] &&-nums[i]-nums[j]!=nums[j]) || it3->second) {
    
25.                         results.emplace_back(vector<int>{nums[i],nums[j],it3->first});
    
26.                         num2s.emplace(it3->first);
    
27.                     }
    
28.                 }
    
29.                 num2s.emplace_hint(it2,nums[j]);
    
30.             }
    
31.             num1s.erase(it1);
    
32.         }
    
33.         if(zeroCnt>=3) results.emplace_back(vector<int>{0,0,0});
    
34.         return results;
    
35.     }
    
36. };

复制代码