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

关键是怎么避免重复，楼主可以尝试用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]);
        }
    }
};

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[i]-nums[j])) {
                    if (map.get(-nums[i]-nums[j]) > j) {
                        ArrayList<Integer> a = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[map.get(-nums[i]-nums[j])]));
                        Collections.sort(a);
                        res.add(a);
                    }
                }
            }
        }
        res = res.stream().distinct().collect(Collectors.toList());
        return res;
    }
}[/i][/i][/i][/i]

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吧? 论坛好像打不出来