双指针题目

1在原数据上直接修改更省空间

面试题 10.01. 合并排序的数组

2可以直接推导数学公式解,也可以用双指针法,还没写代码

面试题57 - II. 和为s的连续正数序列

3 可以证明移动左右指针中较大的一定不会达到最优解,或者说移动没有意义,故每次移动较小的,这种题的暴力解法是用二维dp,但时间复杂度是n方,

11. 盛最多水的容器

4 这个题非常类似于阿里笔试求连续子数组最大值期望的题,都是利用指针进行朝左朝右扩展,这个题先统计奇数的索引并存储,再进行遍历求积,

1248. 统计「优美子数组」

5 这个题的双指针不明显,勉强算是,官方的讨论技巧非常巧妙,无需讨论五种情况,实际上是先把区间的交集求出来,如果是空集,可直接由两个端点判断出来,

986. 区间列表的交集

6 必须要先排序,再用双指针进行遍历,一旦和为0了,注意要去重,即如果相等就移动指针,

15. 三数之和

7 竞技世界笔试题第一道,

注意审题!注意审题!注意审题!题中说给定一个含有 个正整数的数组和一个正整数s,数组中全是正数,没有负数,用双指针求解时要先确定是两个指针的起始位置是再同一边还是左端一个右端一个,这个题实际上是双指针结合贪心算法,先移动右指针,直到和大于目标值了,再移动左指针,之所以可以这么左是因为都是正数, 如果含有负数了,则需要用二维动态规划的方法,复杂度为n方,

对于连续问题首先要想到双指针和二维动态规划的方法,

209. 长度最小的子数组

ttt

原文地址:https://www.cnblogs.com/xxswkl/p/12401705.html