求解3Sum without sort，O(n^2)

看到FB的followup，喜欢问，请问有什么思路吗？

关键是怎么避免重复，楼主可以尝试用map[nums[i], count]记录frequency，然后把map里所有的key放在一个vector里，重复的会连在一起，这样就可以避免重复了
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size() < 3) return res;
        unordered_map<int, int> mp;
        for(int i : nums)
            mp[i]++;
        vector<int> arr(nums.size());
        int k = 0;
        for(auto& it : mp) {
            for(int i = 0; i < it.second; i++) {
                arr[k++] = it.first;
            }
        }
        
        vector<int> tmp;
        for(int i = 0; i <= arr.size() - 3; i++) {
            if(i != 0 && arr[i] == arr[i - 1]) continue;
            tmp.push_back(arr[i]);
            twoSum(arr, i + 1, arr.size() - 1, tmp, res, -arr[i]);
            tmp.pop_back();
        }
        return res;
    }
private:
    void twoSum(vector<int>& arr, int start, int end, vector<int>& tmp, vector<vector<int>>& res, int target) {
        unordered_set<int> st;
        unordered_set<int> visited;
        
        for(int i = start; i <= end; i++) {
            if(st.find(target - arr[i]) != st.end() && visited.find(target - arr[i]) == visited.end()) {
                tmp.push_back(target - arr[i]);
                tmp.push_back(arr[i]);
                res.push_back(tmp);
                tmp.pop_back();
                tmp.pop_back();
                visited.insert(arr[i]);
                visited.insert(target - arr[i]);
            }
            st.insert(arr[i]);
        }
    }
};

Since it does not allow to sort the array, I assume it only asks for one triplet as solution or returns an empty triplet if no such sum exists. Also, I don't think using Hash map to store value to index works since the given array could have duplicates. I would recommend to use Hash map to store value to frequency.

1. 
   
2. vector<int> find3Sum(vector<int>& a, int target)  {
   
3.   int n = a.size();
   
4.   if (n < 3) return vector<int>();
   
5.   unordered_map<int,int> freq;
   
6.   for (auto& x:a) freq[x]++;
   
7.   for (int i = 0; i < n-1; i++) {
   
8.     for (int j = i+1; j < n; j++) {
   
9.       int residual = target - a[i] - a[j];
   
10.       if (freq.count(residual)) {
    
11.         int duplicity = 0;
    
12.         if (residual == a[i]) duplicity++;
    
13.         if (residual == a[j]) duplicity++;
    
14.         if (freq[residual] > duplicity) return {a[i], a[j], residual};
    
15.       }
    
16.     }
    
17.   }  
    
18.   return vector<int>();
    
19. }
    

复制代码

hkc593 发表于 2016-9-14 11:03
怎么处理[-1,-1, 2]能

这不是能正常处理吗？两层loop，找到－1，－1时，发现2在map里并且2的index = 2比前两个都要大，存下这个结果。

用2Sum without sort做，外层套个循环就是了

就用HashMap存<num, index>就行了，然后用两层loop，在Map里找target - num1 - num2的值并且index > i1 && index >2

不sort就hash

Two sum hashes O(n) + for loop

iPhD 发表于 2016-9-14 03:38
就用HashMap存就行了，然后用两层loop，在Map里找target - num1 - num2的值并且index > i1 && index >2

怎么处理[-1,-1, 2]能

zzgzzm 发表于 2016-9-14 10:37
Since it does not allow to sort the array, I assume it only asks for one triplet as solution or retu ...

既然是3sum的follow up，我想应该是写成和3sum同样的结果吧。

iPhD 发表于 2016-9-14 03:38
就用HashMap存就行了，然后用两层loop，在Map里找target - num1 - num2的值并且index > i1 && index >2

[-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0], 按照你的方法好像会出现[1, 4, -5]和[4, 1 ,-5]这种重复的情况

iPhD 发表于 2016-9-14 03:38
就用HashMap存就行了，然后用两层loop，在Map里找target - num1 - num2的值并且index > i1 && index >2

有代码吗？ 能否贴出来，学习一下？ 谢谢

有java 版本的代码吗？ 学习一下

JimmyZhuang 发表于 2016-9-15 00:57
关键是怎么避免重复，楼主可以尝试用map[nums, count]记录frequency，然后把map里所有的key放在一个vector ...

但是这样开始时相当于counting sort的一部分 是不？不知道这样允许不

forestwn 发表于 2016-10-8 14:18
但是这样开始时相当于counting sort的一部分 是不？不知道这样允许不

这个就得问面试官了>－<

JimmyZhuang 发表于 2016-10-9 02:04
这个就得问面试官了>－

Thanks for sharing! :)

我想到一个解法  可以用string来编码三个点 比如"1#5#6" 从小到大
所有的解对应的string 放进set 就可以避免重复了

JimmyZhuang 发表于 2016-9-15 00:57
关键是怎么避免重复，楼主可以尝试用map[nums, count]记录frequency，然后把map里所有的key放在一个vector ...

有谁试过这个方法，面试官允许用这个方法吗

everest8848 发表于 2017-10-29 15:45
有谁试过这个方法，面试官允许用这个方法吗

没有在面试中试过，自己曾经写过。面试官允许不允许用，得面试官说了算。

O(N^2) 最坏情况[0,0,0,0,0] 是O(N^3)
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i ++) {
            map.put(nums, i);
        }
        for (int i = 0; i < nums.length-1; i ++) {
            for (int j = i+1; j < nums.length; j ++) {
                if (map.containsKey(-nums-nums[j])) {
                    if (map.get(-nums-nums[j]) > j) {
                        ArrayList<Integer> a = new ArrayList<>(Arrays.asList(nums, nums[j], nums[map.get(-nums-nums[j])]));
                        Collections.sort(a);
                        res.add(a);
                    }
                }
            }
        }
        res = res.stream().distinct().collect(Collectors.toList());
        return res;
    }
}

e5399014 发表于 2017-11-8 05:50
O(N^2) 最坏情况[0,0,0,0,0] 是O(N^3)
class Solution {
    public List threeSum(int[] nums) {

你这里的nums指的是nums_i吧? 论坛好像打不出来