🤖 AI文章摘要 qwen-turbo-latest
加载中...

双指针

双指针用于同时标记两个元素或者一段数据的边界,例如可变滑动窗口方法中就是使用双指针划定边界的。

假设左指针为$i$,右指针为$j$

  • $i$的初始位置通常分布于开头。$j$的初始位置可分布于开头或结尾,根据问题背景确定分布。
  • $i$和$j$的移动一般是单向的,迭代需要注意确保不会漏掉任一情况。

使用示例

双指针示例1

升序数组arr中是否有两个元素的和等于目标值k
传统的思路是数组中元素两两配对求和与k进行比较,这个方法的时间复杂度为$O(n^2)$。可以发现并没有使用到升序数组的特性,使用双指针方法合理忽略相对应的元素可以提高计算效率。