本文讲解常见算法技巧-滑动窗口(双指针),附有三道题。
参考视频:滑动窗口【基础算法精讲 03】
https://www.bilibili.com/video/BV1hd4y1r7Gq
题单:
- 长度最小的子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/solution/biao-ti-xia-biao-zong-suan-cuo-qing-kan-k81nh/
- 无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/xia-biao-zong-suan-cuo-qing-kan-zhe-by-e-iaks/
- 乘积小于 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)