高盛 K pair two sum

普通版本的Two Sum 用一个HashMap, 然后iterate array一次就可以了。但是找K pair two sum 难的多。

比如说[1,2,3,1,8,1] 找 sum = 2的。 有[1,1], [1,1], [1,1] 三组。

这里要用到类似于3 Sum的双指针算法。 首先给Array排序, 排序完以后 用两个指针, front & end走.

每一轮 front 会把end指针不断往前移动找出所有以当前front 为一个element,end 另一个的符合target的组合。

然后front 移动下一位,end repeat process。。。

O(nlogn)


最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,779评论 0 33
  • 前言: 详细介绍: List:元素有放入顺序,元素可重复Map:元素按键值对存储,无放入顺序Set:元素无放入顺序...
    YBshone阅读 8,732评论 0 17
  • 前言 把《C++ Primer》[https://book.douban.com/subject/25708312...
    尤汐Yogy阅读 9,542评论 1 51
  • 古人曾浩叹:“无计留春住!”其实,留不住的岂止是春,难道夏、秋、冬就能留得住吗?之所以说无计留春住,只不过是文人墨...
    听风阁主人阅读 580评论 3 5
  • 我还是孩子,却遭遇了~目睹了~承受了~~~还有什么比亲眼看着自己的亲人离世更加痛苦的呢,您是潇洒的离开了,可我.....
    錵落阅读 167评论 0 0