分类: LeetCode OJ

评分 0, 满分 5 星
0 票

和3Sum一模一样,3Sum枚举第一个值,4Sum枚举前两个,扫描后两个,复杂度O(n^3)。

评分 0, 满分 5 星
0 票

和3Sum的思路一样,这个题目不用维护结果集,双指针的方向是根据当前sum和target的接近程度调整的,当结果更好的时候更新结果。

评分 0, 满分 5 星
0 票

首先排序。

其次枚举第一个数,双指针扫描求解另外的两个数。

复杂度O(n^2),应该是本题的最优解了。刚开始交的时候却T了好几发,因为在答案集中加入了重复项,去重写渣了。

评分 0, 满分 5 星
0 票

好久之前做的了,没想到上周视频会议的时候被问到。提问我的是一美国教授,讲起话来非常平易近人,可是突然让我在身后的白板上写这个题的完整程序还是紧张了一下子的。考虑了树的同构,用 dfs + 各种判断也算一气呵成的写完了,还得到一个“非常好”的口头赞扬。今天再看原来写的程序,原来无脑判就能通过了。

评分 0, 满分 5 星
0 票

相比于前一个问题,这个题目允许出现重复数字,那么就不可以简单地根据mid位置的数字与当前已知的最小数字进行比较大小来划分答案所在的区间,主要指相等的情况。比如序列一:3 3 3 3 1 3,序列二:3 1 3 3 3 3。比较num[mid] = num[2]与num[r] = num[5],发现答案有可能在任意一区间,此时,两区间的最小就一定是答案了。用递归比较容易完成。

评分 0, 满分 5 星
0 票

这道题最初是Sure讲给我的,后来在LeetCode碰到了,好题。

方法一:借助插入排序的思想,复杂度O(m + n)。用两个指针分别指向两个数组的首地址(用两个代表数组下标的变量,不妨设idx_a,idx_b,初始为0),然后比较A[idx_a]和B[idx_b]的大小,值小的下标向后移动一个位置(idx_a++或idx_b++),然后继续比较,直到当前idx_a或者idx_b位置恰好处在两个数组的中间位置,记录下当前位置的值就是结果。至于m+n的奇偶情况对应处理就好。

评分 5.00, 满分 5 星
1 票

方法一:最直观的想法,暴力枚举。复杂度O(n^2),没有提交,目测超时。

方法二:排序+双指针扫描。复杂度O(nlogn)。开一个结构体记录原来数组的值和下标,对值排序,双指针扫描结构体的值,相应的下标就是结果。