0%

滑动窗口(双指针)

本文讲解常见算法技巧-滑动窗口(双指针),附有三道题。

参考视频:滑动窗口【基础算法精讲 03】

https://www.bilibili.com/video/BV1hd4y1r7Gq

题单:

  1. 长度最小的子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/solution/biao-ti-xia-biao-zong-suan-cuo-qing-kan-k81nh/
  2. 无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
  3. 乘积小于 K 的子数组 https://leetcode.cn/problems/subarray-product-less-than-k/solution/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-jebq/

重要思想是尽可能避免暴力破解时,第二个指针无法利用原先结果,只能从第一个指针处开始遍历的问题;

O(n^2)

利用滑动窗口后,两个指针分别过一次数组即可

O(n)