双指针 Two Pointers

”多指针“做法算是一种技巧,一般可以分为:

  • 普通双指针:两个指针往同一个方向移动;

  • 对撞双指针:两个指针面对面移动;

  • 快慢双指针。

    如在检测环形链表的做法中,慢指针每次移动一步,快指针每次移动两步。

如,a = [1, 4, 5, 7, 9],找到两个不同的数之和为12:

  • 普通双指针:O(N2)O(N^2)
  • 对撞双指针:得益于a是一个有序数组,这种做法只需O(N)O(N)

例题

  • [x] 141:环形链表(Linked List Cycle)
  • [ ] 881:救生艇(Boats to Save People)