一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1127|回复: 15
收起左侧

[算法题] 求解3Sum without sort,O(n^2)

[复制链接] |试试Instant~ |关注本帖
hkc593 发表于 2016-9-13 22:14:03 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
看到FB的followup,喜欢问,请问有什么思路吗?

tamitito 发表于 2016-9-14 03:25:51 | 显示全部楼层
用2Sum without sort做,外层套个循环就是了
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-9-14 03:38:13 | 显示全部楼层
就用HashMap存<num, index>就行了,然后用两层loop,在Map里找target - num1 - num2的值并且index > i1 && index >2
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-14 03:39:05 | 显示全部楼层
不sort就hash
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-14 10:37:09 | 显示全部楼层
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. vector<int> find3Sum(vector<int>& a, int target)  {
  2.   int n = a.size();
  3.   if (n < 3) return vector<int>();
  4.   unordered_map<int,int> freq;
  5.   for (auto& x:a) freq[x]++;
  6.   for (int i = 0; i < n-1; i++) {
  7.     for (int j = i+1; j < n; j++) {
  8.       int residual = target - a[i] - a[j];
  9.       if (freq.count(residual)) {
  10.         int duplicity = 0;
  11.         if (residual == a[i]) duplicity++;
  12.         if (residual == a[j]) duplicity++;
  13.         if (freq[residual] > duplicity) return {a[i], a[j], residual};
  14.       }
  15.     }
  16.   }  
  17.   return vector<int>();
  18. }
复制代码
回复 支持 反对

使用道具 举报

gaocan1992 发表于 2016-9-14 11:00:28 | 显示全部楼层
Two sum hashes O(n) + for loop
回复 支持 反对

使用道具 举报

 楼主| hkc593 发表于 2016-9-14 11:03:31 | 显示全部楼层
iPhD 发表于 2016-9-14 03:38
就用HashMap存就行了,然后用两层loop,在Map里找target - num1 - num2的值并且index > i1 && index >2

怎么处理[-1,-1, 2]能
回复 支持 反对

使用道具 举报

 楼主| hkc593 发表于 2016-9-14 11:04:15 | 显示全部楼层
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 11:28:56 | 显示全部楼层
hkc593 发表于 2016-9-14 11:03
怎么处理[-1,-1, 2]能

这不是能正常处理吗?两层loop,找到-1,-1时,发现2在map里并且2的index = 2比前两个都要大,存下这个结果。
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-9-14 13:03:59 | 显示全部楼层
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]这种重复的情况
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-9-15 00:57:47 | 显示全部楼层
关键是怎么避免重复,楼主可以尝试用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]);
        }
    }
};
回复 支持 反对

使用道具 举报

fcwrme 发表于 2016-9-26 11:39:11 | 显示全部楼层
iPhD 发表于 2016-9-14 03:38
就用HashMap存就行了,然后用两层loop,在Map里找target - num1 - num2的值并且index > i1 && index >2

有代码吗? 能否贴出来,学习一下? 谢谢
回复 支持 反对

使用道具 举报

liyoulu 发表于 2016-9-26 13:03:50 | 显示全部楼层
有java 版本的代码吗? 学习一下
回复 支持 反对

使用道具 举报

forestwn 发表于 2016-10-8 14:18:56 | 显示全部楼层
本帖最后由 forestwn 于 2016-10-8 14:20 编辑
JimmyZhuang 发表于 2016-9-15 00:57
关键是怎么避免重复,楼主可以尝试用map[nums, count]记录frequency,然后把map里所有的key放在一个vector ...

但是这样开始时相当于counting sort的一部分 是不?不知道这样允许不
回复 支持 反对

使用道具 举报

JimmyZhuang 发表于 2016-10-9 02:04:44 | 显示全部楼层
forestwn 发表于 2016-10-8 14:18
但是这样开始时相当于counting sort的一部分 是不?不知道这样允许不

这个就得问面试官了>-<
回复 支持 反对

使用道具 举报

forestwn 发表于 2016-10-9 02:33:42 | 显示全部楼层
JimmyZhuang 发表于 2016-10-9 02:04
这个就得问面试官了>-

Thanks for sharing! :)

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 17:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表