📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: ilovetennis
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] 关于4 Sum O(n^2logn)解法的问题

🔗
 楼主| ilovetennis 2014-8-8 08:57:59 | 只看该作者
全局:
本帖最后由 ilovetennis 于 2014-8-8 09:19 编辑
Kimurate 发表于 2014-8-8 00:45
key是2sum的值,那就还是hash碰撞,这里的hash有两层,第二层没碰撞罢了,但你说的这种值一样,元素组成 ...

数组排好序了,和还是有可能是一样的吧?比如: S = {1, 2, 3, 4, 5, 6, 7, 8} 。 考虑i = 6 时,因为1+6 = 2+5 = 3+4 = 7, 所以对应于7的set里存在有三组pair,当j = 7, target = 22时,  此时 a = S[6] + S[7] = 15, target - a = 7, hash[7]这个set里就有三组pair,第三层for循环就要跑三次了。换个角度看,如果这种和相同的情况没有,那也没有必要用set了吧, 第三层for循环又有什么意义呢?
回复

使用道具 举报

🔗
Kimurate 2014-8-8 10:56:57 | 只看该作者
全局:
ilovetennis 发表于 2014-8-7 16:57
数组排好序了,和还是有可能是一样的吧?比如: S = {1, 2, 3, 4, 5, 6, 7, 8} 。 考虑i = 6 时,因为1+6 ...

咳咳,不可能的,你没仔细看那个c++代码的逻辑。
i=6时,不是1+6, 2+5, 3+4, 而是1+6, 2+6,3+6, ... 5+6, 所以一次循环里,不存在一个和对应多个二元组的情况。
用set是因为从[1,1,1,1,2,2,2] 取出和为6的四元组时,会有很多重复的四元组。
回复

使用道具 举报

🔗
 楼主| ilovetennis 2014-8-8 12:15:09 | 只看该作者
全局:
Kimurate 发表于 2014-8-8 10:56
咳咳,不可能的,你没仔细看那个c++代码的逻辑。
i=6时,不是1+6, 2+5, 3+4, 而是1+6, 2+6,3+6, ... 5+ ...

我的理解是: i 是 从 0 开始循环的, i 值达到 6 之前必然先经过5, 而i = 5 时 1+ 6, 2 + 6, 3 + 6 ... 5 + 6 被放入相应set; i = 4 时是1 +  5, 2 + 5, 3 + 5, 4 + 5 被放入相应set 。 所以 i = 6 时, hashtable中存有前边所有两两组合的pair, 这样做也才是保证不丢解。
回复

使用道具 举报

🔗
Kimurate 2014-8-8 12:58:34 | 只看该作者
全局:
ilovetennis 发表于 2014-8-7 20:15
我的理解是: i 是 从 0 开始循环的, i 值达到 6 之前必然先经过5, 而i = 5 时 1+ 6, 2 + 6, 3 + 6 ...  ...

恩,有道理。这个O(n^3)应该是最坏情况,但即便从构造的例子中来看,这个情况也是非常局部的,不知道能否扩展到整体,把整个算法都变成O(n^3)。
两部分的2sum只会越来越大,和跟二元组不会总有很多重复的。感觉上重复二元组的数量好像是先从少变多,然后又变少了,应该不是O(n),但我不知道怎么证明。

详细看看这个 http://cs.stackexchange.com/ques ... -3sum-k-sum-problem

好多细节我还是没搞懂啊 = =。
回复

使用道具 举报

🔗
3652ltc 2014-8-9 12:53:39 | 只看该作者
全局:
我觉得关键是 如何在n^2logn复杂度下生成不含重复元素的 pairs
knuth好像有写过generate all combinations 我也没太懂,还希望lz多多指教指教,我想了半天实在没啥思路。。哭
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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