F家常考的3sum的变形题到底是啥意思啊？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

F家常考的3sum的变形题到底是啥意思啊？

F家常考的3sum的变形题到底是啥意思啊？# JobHunting - 待字闺中

y*e2015-03-02 08:03

1 楼

就看了两个面经，竟然都有这题，可以原题作者都说的一笔带过，
一个说的是
“three sum的变种, 允许3个数字重复，就是起始位置一样就行”
另一个说的是
“3sum, 可以重用数字”
是说比如-2,4,6,1,2,0取三数和为0的话，那么
-2,-2,4
-2,2,0
-2,1,1
0，0，0
都是合理解吗？

d*62015-03-02 08:03

2 楼

应该不是这个意思，是原来的array里有重复的话结果允许重复
比如 -2,4,6,1,2,0,0
-2,2,0
-2,2,0
两个解，第一个和第二0不一样
这是我比较leetcode上原题后的理解，不一定对
但此题应该不难，只要读懂题目，怎么变都能搞定

y*e2015-03-02 08:03

3 楼

那这句话“就是起始位置一样就行”应该是起始位置不一样就行？少打了不字？

【在 d**********6 的大作中提到】

: 应该不是这个意思，是原来的array里有重复的话结果允许重复
: 比如 -2,4,6,1,2,0,0
: -2,2,0
: -2,2,0
: 两个解，第一个和第二0不一样
: 这是我比较leetcode上原题后的理解，不一定对
: 但此题应该不难，只要读懂题目，怎么变都能搞定

h*k2015-03-02 08:03

4 楼

0，0，0应该也是合理解
感觉就是dfs 递归的时候下一个index取一样的

y*e2015-03-02 08:03

5 楼

用recursion的话会不会complexity太大？我觉得sort + two pointer的基础上改应该
就可以，就是不知道题目的意思到底是啥？

【在 h***k 的大作中提到】

: 0，0，0应该也是合理解
: 感觉就是dfs 递归的时候下一个index取一样的

f*a2015-03-02 08:03

6 楼

i think ur original interpretation is correct?
my stab at it:
sort ...
for (int i = 0; i < n; i++) {
int j = i;
int k = n-1;
while (j <= k) {
j++ or k-- depends on the diff
}
}

【在 y*****e 的大作中提到】

: 用recursion的话会不会complexity太大？我觉得sort + two pointer的基础上改应该
: 就可以，就是不知道题目的意思到底是啥？

y*e2015-03-02 08:03

7 楼

我的思路也是这样：）谢谢分享！

/* */) 的大作中提到: 】

【在 f********a 的大作中提到】

: i think ur original interpretation is correct?
: my stab at it:
: sort ...
: for (int i = 0; i < n; i++) {
: int j = i;
: int k = n-1;
: while (j <= k) {
: j++ or k-- depends on the diff
: }
: }

f*a2015-03-02 08:03

8 楼

不过，你知不知道如果用back tracking那种方法做，复杂度是O 什么？

【在 y*****e 的大作中提到】

: 我的思路也是这样：）谢谢分享！
:
: /* */) 的大作中提到: 】