在我们处理有序的数组并需要找到一组满足某些约束的元素的问题中,双指针方法可以首先考虑。
元素集可以是一对、一个三元组甚至是一个子数组。 例如,看看下面的问题:

给定一个排序数字数组和一个目标总和,在数组中找到一个总和等于给定目标的对。

为了解决这个问题,我们可以一个一个地考虑每个元素(由第一个指针指向)并遍历剩余的元素(由第二个指针指向)以找到具有给定总和的对。 该算法的时间复杂度为 O(N^2)

鉴于输入数组已排序,一种有效的方法是从一个指针开始,另一个指针在末尾。 在每一步,我们将查看两个指针指向的数字加起来是否等于目标总和。 如果他们不这样做,我们将做以下两件事之一:

如果两个指针指向的两个数之和大于目标和,这意味着我们需要一个和较小的对。 因此,要尝试更多对,我们可以减少结束指针。
如果两个指针指向的两个数之和小于目标和,这意味着我们需要一个和更大的对。 因此,要尝试更多对,我们可以增加起始指针。
具体流程如下图

问题的关键

1.首先要看给定的数组是否是有序的
2.其实滑动窗口也算是双指针的一种,有时候可以考虑双指针的解法
后面列出几个典型问题,并指出问题的核心

简单题目
中等题目