s********s
发帖数: 49 | 1 代码好长啊。。。其实有了2sum,3sum的做法很直观吧：先取出一个数，那么只要在剩
下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)就可以了吧。
所以3sum就退化成了2sum, 取出一个数字，这样的数字有N个，所以3sum的算法复杂度
就是O(N^2 )。
注意你排序只需要排一次，后面的工作都是取出一个数字，然后找剩下的两个数字，找
两个数字是2sum用头尾指针线性扫，这里很容易错误的将复杂度算成O(N^2 log N)，这
个是不对的。
可以参考这个总结 http://tech-wonderland.net/blog/summary-of-ksum-problems.html |
|
y*d
发帖数: 2226 | 2 3sum的思路可以用于2sum，但是用在2sum上就是脱了裤子放屁
因为2sum有1万种解法都是nlogn的
4sum也许有更神奇的解法
我知道的就是在3sum基础上再乘n |
|
s*******m
发帖数: 228 | 3 2Sum, 3Sum, 4Sum
稍微有点变化的是, array中数字是0-10, target也是0-10的. 要求输出在数组中最先
遇到的
满足条件的
pair(2sum)
triplet(3sum)
4个数字组(4sum) |
|
a*****t
发帖数: 30 | 4 The 3sum problem is defined as follows:
given a set S of n integers, dothere exist three elements {a, b, c} 2 S such
that a + b + c = 0?
This is a linear satisfiability problem. 3sum can be solved using a simple
algorithm with O(n^2) runtime (sort S, then test 3-tuples intelligently).
我不是特别清楚如何 "test 3-tuples intelligently" in O(n^2).
能给点意见吗？ 多谢 |
|
c*********t
发帖数: 2921 | 5 看到最近有人问4sum的问题，
可是我想如果能对2sum ,3sum的问题弄透了，各种方法都研究一下，4sum应该就是一个
扩展，对吧。
我们能不能先列一下可以解决2sum的所有方法？假设数组中有重复的数。
有种方法是用hashtable,可是我发现有个问题，
比如给定数组 [ 1 2 3 4 5 6 7 8 9],求出之和为 10 (target)的两个数，
用hashtable,我们可以得到
1 9
2 8
3 7
4 6
5 5 <<<<<<<这里好像不对了，因为数组里只有一个5,这个问题该如何处理？
6 4
7 3
8 2
9 1
另外就是得出的组合有重复的，象 1 9, 其实和 9 1 是一回事，该怎么办？
还有哪些常用的方法来解决2sum问题的？
谢谢！ |
|
r*****e
发帖数: 30 | 6 LEETCODE 3SUM 解法
這個是我的N^2 算法
http://pastebin.com/MTJ751ML
二個SOLUTION 都PASS 了 LEETCODE 的TEST， 但是有個問題，就是為什麼我的 N^2
算法 會比 (N^2)(logn)算法 慢？？？
請各位指點一下。 |
|
Z***A
发帖数: 33 | 7 写了3sum的solution，但是没通过OJ large judge，Run Status: Time Limit
Exceeded，请分析一下原因。
下面是code：
public ArrayList> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
if (num.length < 3)
return new ArrayList>();
Arrays.sort(num);
ArrayList> res = new ArrayList
>();
for (int i=0; i < num.length; i++)
{
... 阅读全帖 |
|
a***e
发帖数: 413 | 8 请问大牛，这两道题在skip 相同元素的时候，为什么要用类似
if(x < num.size()-1 & num[x] == num[x+1]) continue; // Skip same
x
而不是 // if( num[x] == num[x-1]) continue;
我自己写的时候是comment out的语句，但总是出错。没搞懂为啥
3sum的代码如下。非常感谢！
vector > threeSum(vector &num) {
vector> result;
sort(num.begin(), num.end());
for (int x = num.size()-1; x >=2; x--) { // Do it backwards
if(x < num.size()-1 & num[x] == num[x+1]) continue; // Skip same
x
// if( num... 阅读全帖 |
|
y*****e
发帖数: 712 | 9 就看了两个面经，竟然都有这题，可以原题作者都说的一笔带过，
一个说的是
“three sum的变种, 允许3个数字重复，就是起始位置一样就行”
另一个说的是
“3sum, 可以重用数字”
是说比如-2,4,6,1,2,0取三数和为0的话，那么
-2,-2,4
-2,2,0
-2,1,1
0，0，0
都是合理解吗？ |
|
|
o*q
发帖数: 630 | 11 # Title Editorial Acceptance Difficulty Frequency
1
Two Sum 28.3% Easy
292
Nim Game 54.4% Easy
344
Reverse String 57.3% Easy
136
Single Number 52.2% Easy
2
Add Two Numbers 25.6% Medium
371
Sum of Two Integers 51.6% Easy
4
Median of Two Sorted Arrays
20.4% Hard
6
ZigZag Conversion 25.6% Easy
13
Roman to Integer 42.7% Easy
237
... 阅读全帖 |
|
l***i
发帖数: 1309 | 12 wikipedia search 3SUM problem. There is no better solution than O(n^2)
currently and there are a number of problems that would have a faster
solution if 3SUM has a better than O(n^2) solution, say O(nlogn). |
|
d********w
发帖数: 363 | 13 First, we can consider 2 numbers, which is O(n) time. We can use 2 two
pointers to process the sorted array or use hashtable to find whether T-cur
in it.
If k = 3, the running time is O(n^2), wiki describes the algorithm http://en.wikipedia.org/wiki/3SUM, it also mentions an optimization
"When the integers are in the range [−u ... u], 3SUM can be solved in
time O(n + u lg u) by representing S as a bit vector and performing a
convolution using FFT." but it is hard to follow.
How about numb... 阅读全帖 |
|
i**********e
发帖数: 1145 | 14 F:
3Sum
Add Binary
Combination Sum
Count and Say
Divide Two Integers
Edit Distance
Implement strStr()
Letter Combinations of a Phone Number
Longest Palindromic Substring
Merge Intervals
Multiply Strings
Next Permutation
Permutations, Permutations II
Regular Expression Matching
Remove Duplicates
Remove Element
Search in Rotated Sorted Array
String to Integer (atoi)
Sqrt(x)
Substring with Concatenation of All Words
Trapping Rain Water
Unique Paths, Unique Paths II
G:
3Sum
Climbing Stairs
Container... 阅读全帖 |
|
|
h********o
发帖数: 14 | 16 我做的跟 3sum 是一个复杂度 O(n^2); 做法也跟 3sum差不错。
1.先sort 数组S，O(nlgn);
2. 使用三个下标 i (当前下标) f(头下标) t(尾下标)
i 从0 到 n-1 遍历 // n 是数组长度
对于每一个i， 设置 f = i+1, t = n-1,
计算 sum = S[i] + S[f] + S[t], 如果比之前的sum更接近，更新。
然后，如果sum 比target 小 ， f++， 否则 t--
对于每一个 i ，以上操作循环至 f>= t, 所以每一个 i 要遍历数组一遍
最终， 第2步的复杂度是 O(n^2)>O(nlgn), 所以这个算法复杂度也是O(n^2) |
|
p*****2
发帖数: 21240 | 17 面试题总结(2) - Two/Three pointers
简称two pointers吧。大概把分类粗略的搞了一遍（http://leetcode.cloudfoundry.com/), 发现利用two pointers解决的题目数量很大。two pointers我指的是一类题，而不一定是真正的two pointers, 比如可能是three pointers, 也可能不是pointer， 而是index。这类题基本上就是发生在array, string, linked list这三种数据结构上，是一种基本的算法和编程技巧，同样超高频率的出现，可以说是面试必遇的题。
two pointers常常和其他的算法混杂起来出现。比如binary search本身也可以归类为
two pointers的。如果这样算的话，Leetcode上边1/4的题目都跟它相关。因此，two
pointers是必须熟练掌握的基本编程技巧。
Two pointers大概分三种类型
1. 两个pointers从头往后走：感觉绝大多数的linked list的题目都涉及到这个操作，
当然还有array。
Imple... 阅读全帖 |
|
|
S******t
发帖数: 151 | 19 这两个题目我一个都不会做……
第一题怎么In-place的nlogn去sort linked list啊...
第二题如果三个数组相同不就基本上可以等价于3SUM么？3SUM没有低于平方阶的算法哎
... |
|
p*****2
发帖数: 21240 | 20
Id Question Difficulty Freqency Data Structures Algorithms
1 Two Sum 2 5
array
set
sort
two pointers
2 Add Two Numbers 3 4
linked list
two pointers
math
3 Longest Substring Without Repeating Characters 3 2
string
hashtable
two pointers
4 Median of Two Sorted Arrays 5 3
array
binary search
5 Longest Palindromic Substring 4 2
string
6 ZigZag Conversion 3 1
string
7 Reverse Integer 2 3
math
8 ... 阅读全帖 |
|
p*****2
发帖数: 21240 | 21 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
p*****2
发帖数: 21240 | 22 好多人问，我就发到这里吧。
面试题的构成和分类
首先声明一下，这里的面试题主要所指数据结构和算法的题目，题目的分析集中在
Leetcode上面的题目上。
我认为一道面试题由以下几个方面组成的
Question
Data structure in question
Data structure in solution
Algorithm in solution
Coding
题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。
问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构
解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。
算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定... 阅读全帖 |
|
l********7
发帖数: 40 | 23 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 M... 阅读全帖 |
|
l********7
发帖数: 40 | 24 前一周电面，电面的题目挺简单，第一题忘了，第二题是two sum，然后写3sum
我写了一个O(n^2)的3sum，然后面试官问我怎么能写到NlogN，但是想了很久都没有想
出来方法，然后面试结束后去wiki一查发现NlogN的方法不存在，应该是面试官记错了
一轮电面之后之后让去onsite
onsite是3轮面试，2轮coding加一轮的experience
coding的题目都很简单，第一个人先是问了我怎么做test，然后出了两题，第一题比较
两个string，返回一个int来表示第一个string大还是第二个string大，只要返回任意
的正数或者负数就行。比如a，ab，就返回一个负数，因为第二个string比第一个
string大
第二题是有这么一个class Contact，里面有一个String的name，和一个List
装着email address，是这个Contact有的address，用一个list装着是因为一个人有可
能有多个email，现在给你an array of Contact，比如
#1 John [j**[email protected]]
#2 M... 阅读全帖 |
|
|
t*******i
发帖数: 4960 | 26 1. 3sum
2. 3sum, 可以重用数学
3. 产生1，2，3，4，5，6，8, 9, 10, 12...这样的序列
(2^a)*（3^b) *（5^c)
产生10^8 个数字，不需要考虑溢出
搞了半天才明白题目
没做出来时间没了 |
|
b******g
发帖数: 3616 | 27 今天正好复习到这题。顺手写了个k-sum的代码，过了LC的3sum和4sum的test。有兴趣帮
着找找有没有没发现的bug。我觉得理解了3sum的算法，并写过4sum以后，这个kSum其
实也就一个小变种，一个葫芦里的药了。由于代码不短，感觉面试的时候还是分成子程
序写比较好，即使时间来不及写完，至少思路能和面试官说清楚。
思路和排板好看点的代码写在自己的复习总结博客里了：
http://bangbingsyb.blogspot.com/2014/11/leetcode-4sum.html
代码：
class Solution {
public:
vector > fourSum(vector &num, int target) {
vector> allSol;
vector sol;
sort(num.begin(),num.end());
kSum(num, 0, num.size()-1, target, 4, sol, allSol);... 阅读全帖 |
|
M******1
发帖数: 90 | 28 给1billion个数字。3sum的要求。有一点不一样就是返回所有小于target的triplet.
但是不准先排序这1billion个数字。
我的想法：
标准3sum都是先排序，然后可以实现n^2的算法。
可是这个要求下，肯定不可以。
除了map reduce还有其他办法么。 |
|
l*y
发帖数: 70 | 29 前言
楼主最近集中面了5家，略有体验。准备过程中从坛子里受益匪浅，希望在此分享面试
经历回馈本版。本来想总结的有条理些，但是又懒又不想太说教所以就以流水账的形式
出现，想到哪里说到哪里，比较混乱您就当看故事了。觉得有用的希望能对您以后面试
有帮助，觉得没用的请您一笑而过。
面经在最后以独立部分列出以便查阅。由于签了NDA并出于尊重面试官的考虑，此部分
不分公司放出 （电面onsite也混合）。
背景
MS毕业后工作7年,最近在马鬃工作. 进马鬃之前在本地小公司厮混也不知本版的高大上
，进马鬃之后偶然间知道这片天地，奋起刷题一年 （有小孩＋工作忙＋自己也有懈怠
）终于做完一遍LC。虽然回首一看有40%左右跟新题一样（完全没印象）但是感觉能力
有所提高，正赶上N家定了onsite遂开始找兄弟们内推，有幸两周半之内安排好另外4家
，聚一周一起面。
公司：F， L， G， I （Intuit） 和 N（Netflix）。
注：楼主至今还没收到offer所以就不谈了。至于以后，如果能有，也不会报去向以及
具体数字，避免争议。多包涵哈。
我的准备之也谈刷题
跟些老朋友聊，刷题刷的是什么？（不是寂寞... 阅读全帖 |
|
b**********5
发帖数: 7881 | 30 对。 我后来写的3sum的变形， 也变为N^3了， 所以我觉得他虽然说3sum，其实就是
考combination sum |
|
A*******i
发帖数: 49 | 31 骑驴找马中，重新刷题，一天也刷不了几道~反正就是尽量挑些有趣的题刷刷，
leetcode上真是有些题看了就反胃，比如什么3sum，4sum，valid Sudoku啥的~原理就
是那么个东西，写起code来又麻烦又无聊
不知道大家都是怎么想的，比如一些题，就说3sum，4sum，就是2sum的思想反复用下，
大家还会去实打实写code吗？面试的时候要是面这种题是不是基本就可以对这个公司呵
呵了 |
|
Q**F
发帖数: 995 | 32 已经挂了
3sum的变体，数字可以重复使用。
一开始按照3sum做的，后来告知可以重复使用，改现有code，输出。
然后问时间空间复杂度。 |
|
发帖数: 1 | 33
谢谢你的回复，觉得可能还是自己面试经验不够吧，今天和fb的HR聊了十分钟也是面试
经验的问题，面试的过程中时间掌握的不好，一开始面试官问我简历上的问题，聊了大
约15分钟，然后开始coding，题目都不难，第一题是3Sum，第二题是N-Queen的变形。
当时收到邮件预约面试的时候告诉我面试时45分钟，第一题3Sum我写完了后，那个面试
官就让我跑test case，一步一步的，然后我就耐心给他跑。第一题完了的时候已经过
去三十七八分钟了，还剩10分钟，我以为不会再有问题了。然后面试官抛出一个N-
Queen，我脑袋停顿了一下，花了大约三四分钟想了一下怎么做，然后开始敲，边敲边
解释，大约到52分钟的时候，我大约完成了70%的时候，面试官说不要写了，时间到了
。然后让我问了几个问题，就结束了。
我都不知道这个面试究竟是45分钟，还是60分钟。我觉得我已经在面试一开始的时候和
面试官确认好，整个电面有多少题目，多长时间。 |
|
z***e
发帖数: 5600 | 34
Start with (n+1)^3-n^3= 3n^2+3n+1
Sum of above = (N+1)^3 = 3Sum n^2 + 3Sum n+ N+1 (sum from n=0 to N)
and we know what Sum n is...
-Z. |
|
s******y
发帖数: 17729 | 35 现在马工搬运厂妹容易了，EB2排期也就三四年，起码的写个3SUM还得会个bst啥的 |
|
发帖数: 1 | 36 忘了这两是啥了。放狗找到以前已经做过。2SUM是faster than 98.86%。3SUM不行，只
比38%的快。 |
|
H***u
发帖数: 1091 | 37 你在你同学面前炫耀会用7种语言写3sum，你同学带俩美女在你面前3some |
|
h*******e
发帖数: 225 | 38 找不到就对了，因为3SUM目前没有人知道o(n^2)的算法，只有在一些特定的model下有
稍微快一点的。 |
|
k***e
发帖数: 556 | 39 2. 我也考虑过 什么时候greedy可以work
dp画表来求用时Nk
3. wiki 3sum，there is no bettern solution than n^2 and there is no better
algorithm for it. |
|
g*******y
发帖数: 1930 | 40 greedy单独用应该不work，可以和回溯结合起来，也许会快一些(?)
dp你是怎么做到NK的？另外值得考虑的一点是,DP的复杂度是伪多项式的。
第3个题，我知道上次讨论过了，3sum是最少要n^2，但是这个勾股数有些不同啊，最显著的一点，满足勾股定理的三个数显然比满足a+b=c的数稀少很多。忘了说了，题目是整数数组。 |
|
|
|
|
|
l***i
发帖数: 1309 | 45 google 3SUM problem, the O(n^2) solution is not hard but takes a while to
get. |
|
|
j**y
发帖数: 462 | 47 找了半天也没找到下面算法
There is a simple algorithm to solve 3SUM in O(n2) time.
有code吗 多谢 |
|
i**********e
发帖数: 1145 | 48 To find an answer where sum of four numbers equal to X, you can do it in O(n
^2) using some extra space. Basic idea is like what LeoZQ said, put all pair
sums in a hash table and search in the hash table. See below for a nice
idea:
http://stackoverflow.com/questions/3569504/find-four-elements-i
However, if you think carefully, if you wish to find all possible
quadruplets that sum to X, the worst case is O(n^3). This is because the
number of combinations grow in the order of O(n^3). (Credits to a... 阅读全帖 |
|
t*********n
发帖数: 89 | 49 2sum,如果用hash table的话，循环中每一次查元素都只在已有的hash table 查，比如
1 -> 此时 hash table为空，则无结果
2 -> 此时 hash table 里有仅有1， 无结果
....
9 -> 此时 hash table 里有{1，2，3，..8},查到1，成立
对于duplicate,我的想法是在hash_table的value以一个bool来表示是否已经用过，即
hash_table myhash。比如数组为{5，5，5}，目标是10
5-> 此时hash table为空，无结果
5-> 此时hash table里面有5，标记myhash[5] = false;
5 -> 此时hash table里面虽然有5，但是myhash[5] = false,则不成立。
请问下大家有没有更巧的方法？ |
|
t****a
发帖数: 1212 | 50 对了，还有另外一个偷懒的技巧
有些DP可以转化为ILP（整数/布尔线性规划）。对于这类题目只要列出约束和目标方程
，直接call gnu的ILP package就可以拿到最优解，程序都不用写了~
版上以前的一些DP题目就可以直接这样用R来解决的，比如背包啦，换硬币，3sum,
4sum之类的
这样的code其实是更加stable更容易维护。就是不知道面试时候这样搞面试官买不买帐 |
|
