2021-02-02

two pointers

广义上的two pointers则是利用问题本身与序列的特性，使用两个下标 i、j 对序列进行扫描（可以同向扫描，也可以反向扫描），以较低的复杂度（一般是O（n）的复杂度）解决问题。

给个例子就明白了：给定一个递增的正整数序列和一个正整数M，求序列中的两个不同位置的数a和b，使得它们的和恰好为M，输出所有满足条件的方案。例如给定序列{1，2，3，4，5，6} 和正整数M = 8， 就存在2 + 6 = 8 与 3 + 5 = 8 成立

。这个做法的复杂度为O（n^2）,如果n在10^5的规模是不可承受的。

复杂度这个高的原因在于：对于一个确定的 a[i] 来说，如果当前的 a[j] 满足 a[i] + a[j] > M , 显然也会有 a[i] + a[ j + 1] > M 和          a[ i + 1 ] + a[ j ] > M成立（因为序列是递增的），因此就不需要对a[ j ] 之后的数进行枚举，如果无视这个性质，就会导致 j 进行大量无效的枚举，效率自然就低下了。

利用two pointers 的思想进行3种选择：使 i 不断向右移动，使 j 不断向左移动，直到 i >= j 成立。

①如果a[ i ] + a[ j ] == M , 由于序列递增，不等式a[ i + 1] + a[ j ] > M 和 a[ i ] + a[ j - 1] < M 均成立，但是a[ i + 1] + a[ j - 1] 与 M 的大小未知，因此可令i = i + 1、j = j - 1（即令 i 向右移动，j 向左移动）。

②如果满足a[ i ] + a[ j ] > M，由于序列递增，不等式a[ i + 1] + a[ j ] > M成立，但是a[ i ] + a[ j - 1] 与M的大小未知，令j = j - 1（即令j 向左移动）。

③如果满足a[ i ] + a[ j ] < M，由于序列递增，不等式a[ i ] + a[ j - 1] < M成立，但是a[ i + 1] + a[ j ] 与M的大小未知，令i = i - 1（即令i 向右移动）。

可以发现，two pointers 的思想充分利用了序列递增的性质，以很浅显的思想降低了复杂度。