标签: 双指针扫描

评分 0, 满分 5 星
0 票

首先O(n)预处理区间和,这样对每一段区间就可以进行O(1)的询问,很直观的一种方法是二分区间长度,总的时间复杂度是O(nlog(n))

评分 0, 满分 5 星
0 票

任选2条线作为边界,和x轴共同组成一个容器。这道题正确理解题意就能想到双指针扫描。

评分 0, 满分 5 星
0 票

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

评分 0, 满分 5 星
0 票

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

评分 0, 满分 5 星
0 票

首先排序。

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

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

评分 5.00, 满分 5 星
1 票

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

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