C*******a
发帖数: 448 | 1 3sum 4sum都是最内圈用sort and squeeze，能省一个O(n)，没什么特殊的吧。 |
|
|
i******s
发帖数: 301 | 3 枚举所有pair, 一共有n*(n-1) / 2个，然后转化为求2sum。重点是去重，可以在pair
里面记录在原来数组的index。所以最好是O(n^2)吧。你的解法应该是O(n^3) |
|
|
|
z***m
发帖数: 1602 | 6 如果不用hash来缓存2个数的话，用排序的方法，应该是O(max(nlogn, n^(k-1))), 4-
sum就是n^3了 |
|
f*****u
发帖数: 308 | 7 k-sum: 给定一个数组A, A中无重复数字,且都是正整数,k,target是某两个给定数,求A
中所有可能的k个数,其和等于target.也就是2sum,3sum,4sum等等的通解. |
|
y*********i
发帖数: 19 | 8 这个问题如果不用特殊数据结构的话，貌似好几十年前就研究过了
k为偶数，k/2个数为一组（4sum时就是算出每个pair的和，共n^2个），排序，然后two
pointe前后往中间走，复杂度n^(k/2)logn
k为奇数，需要多一重循环，n^(k/2） |
|
|
|
c*******0
发帖数: 162 | 11 这个代码O(n^3), 但不超时。
vector > fourSum(vector &num, int target) {
vector > rst;
if(num.size() <= 3) return rst;
std::sort(num.begin(), num.end());
int len = num.size();
for(int i = 0; i < num.size() - 3; i++){
if(i > 0 && num[i] == num[i-1]) continue;
for(int j = i + 1; j < num.size() - 2; j++){
if(j > i + 1 && num[j] == num[j-1])continue;
int l = j + 1, r = len - 1;
... 阅读全帖 |
|
g********c
发帖数: 23 | 12 有没有O（n^2 * lg n）的代码呢？网上都说自己的复杂度低，可是一看都很高 |
|
x********u
发帖数: 1061 | 13 我感觉不可能有最差O（n^2 * lg n）算法，最多是期望能达到这个 |
|
|
|
|
c********t
发帖数: 5706 | 17 应该是 O(n^2 * m)吧 m is average duplicate 2sum number
1，2，3，4，5，6
target 14
要找出所有解，肯定要处理2sum的duplicate |
|
|
i*****r
发帖数: 265 | 19 quick sort 一直是n^2。只是一般情况下run的比nlgn的都快而已 |
|
c********t
发帖数: 5706 | 20 人生观颠覆了，面试的时候，一旦有sort，我都是告诉是O(nlogn) 复杂度，面试官从
没异议。 难道以后面试当问到复杂度的时候，每次都要说清楚average, worst case
和 best case啊，很耽误时间的。 |
|
s*a
发帖数: 267 | 21 尽量用theta，theta是average复杂度。 |
|
s**********g
发帖数: 14942 | 22 一般说average的O问题应该不大
但是如果能同时说出worst的O，应该可以加分
如果面试官想问worst O，可能会follow up问。。 |
|
o*q
发帖数: 630 | 23 # 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
... 阅读全帖 |
|
f****e
发帖数: 923 | 24 这样为什么能去重呢, 看到3sum, 4sum, subset, 和permutation 里面很多这样写来去
重的?
我原来以为是因为 nums[i] 和 nums[i-1] 相同,
https://discuss.leetcode.com/topic/19845/java-solution-using-dfs-easy-
understand/16
cuyuan
Reputation: 3
For those who don't understand how to avoid duplicate by:
if "(i > cur && cand[i] == cand[i-1]) continue;
when we should skip a number? not just it's the same as previous number, but
also when it's previous number haven't been added!
i > cur means cand[i - 1] is not added to the path (you should kn... 阅读全帖 |
|
发帖数: 1 | 25 2sum，应该是个初始题吧。目测套路为5分钟搞定，然后后面估计会3sum，4sum吧。送
分题了，现在这个年头不刷题就面fg，醉了醉了啊。 |
|
i*****d
发帖数: 962 | 26 先问个3sum热热身，再问问4sum，5sum，一直问到N sum |
|
|
f****p
发帖数: 18483 | 28
你连4sum都做不出来，又跑来了你，你是没救了，赶紧搬尼姑庵去吧～
连少林寺那个主持都。。。你赶紧去，你还有机会！ |
|
z****e
发帖数: 54598 | 29
老姜，这里如果有个回路呢？
其次，你在2sum的选择会影响到后面3sum, 4sum这些的选择数值
这不是独立的好吧？ |
|
z****e
发帖数: 54598 | 30 老姜，我说过了，当最优解不存在的时候
你需要把你的所有的组合全部过一遍
你自己算算这里复杂度有多少
你穷举一下看有多少种组合呵呵
尤其是4sum, 5sum的时候 |
|
|
