目录

力扣总结 常见算法(四):双指针和滑动窗口

双指针算法一般指两个指针在数组上相向移动来解决问题的算法。

双指针算法常应用在具有某种有序性质的问题上,本质上是一种减少了搜索范围的递归。

广义来说,用两个变量在线性结构上遍历来解决问题的方法都可以归为双指针算法。 比如链表上的快慢指针、部分滑动窗口问题。

用双指针来解决滑动窗口问题时,两个指针同向移动,常应用在某种限制条件下的窗口最值问题。

有些滑动窗口问题更加复杂,还需要用到 有序集合滚动哈希 等方法,这里暂不涉及。

1 基础

  • 0003 无重复字符的最长子串
  • 0167 两数之和 II - 输入有序数组
  • 0209 长度最小的子数组
  • 0345 反转字符串中的元音字母
  • 0643 子数组最大平均数 I

2 进阶

  • 0011 盛最多水的容器
  • 0016 最接近的三数之和
  • 0424 替换后的最长重复字符
  • 0438 找到字符串中所有字母异位词
  • 0713 乘积小于K的子数组

3 挑战

  • 0030 串联所有单词的子串
  • 0042 接雨水
  • 0076 最小覆盖子串
  • 0992 K 个不同整数的子数组