双指针(Two pointers)有两大类
情况一: 两个指针指向两个不同的序列, 比如归并排序
情况二: 两个指针指向同一个序列, 这种出现的更多一些, 比如快排
一般的写法只有一种:
|
|
解释: 让i把数组扫描一遍, j与i以某种性质维护一个区间
解题思路: 先用朴素算法O(N^2)来暴力解决问题, 然后看i j之间他们有没有单调关系, 有单调关系则利用单调关系套用模板把整个枚举的状态数量从N^2变为N
双指针(Two pointers)有两大类
情况一: 两个指针指向两个不同的序列, 比如归并排序
情况二: 两个指针指向同一个序列, 这种出现的更多一些, 比如快排
一般的写法只有一种:
|
|
解释: 让i把数组扫描一遍, j与i以某种性质维护一个区间
解题思路: 先用朴素算法O(N^2)来暴力解决问题, 然后看i j之间他们有没有单调关系, 有单调关系则利用单调关系套用模板把整个枚举的状态数量从N^2变为N