定义

滑动窗口只是形象的表述，其本质应该算是一种双指针。
两个指针对应窗口的左右边界，一般情况右指针先走，当窗口大小不满足或者一些条件不满足时，左指针移动，使窗口内元素满足题目条件。
不使用双指针，也可以使用多层for循环的形式，使用双指针，时间复杂度变成o(n)，相当于使用脑力换时间。

适用范围

  • 1、一般是字符串或者数组

  • 2、一般是要求最值（最大长度，最短长度等等）或者子序列

    算法思想

    1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
    2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。
    3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。
    4、重复第 2 和第 3 步，直到 right 到达序列的尽头。

    算法模板

    单层循环

    1. def template():
    2.   # 初始化滑动窗口两端
    3.   left = right = 0
    5.   # 序列及序列长度
    6.   seq, seq_len = xx, xx
    8.   # 滑动窗口序列
    9.   slide_win = []
    11.   # 结果值
    12.   rst = xx
    14.   while right < seq_len:
    15.       slide_win.append(seq[right])
    16.       # 还没找到一个可行解
    17.       if not avaliable(slide_win):
    18.           # 扩大窗口
    19.           right += 1
    20.       else:
    21.           # 找到一个可行解，更新结果值
    22.           rst = update()
    23.           # 缩小窗口
    24.           left += 1

    多层循环

    1. def template():
    2.   # 初始化滑动窗口两端
    3.   left = right = 0
    5.   # 序列及序列长度
    6.   seq, seq_len = xx, xx
    8.   # 滑动窗口序列
    9.   slide_win = []
    11.   # 结果值
    12.   rst = xx
    14.   while right < seq_len:
    15.       slide_win.append(seq[right])
    16.       # 还没找到一个可行解
    17.       if not avaliable(slide_win):
    18.           # 扩大窗口
    19.           right += 1
    20.           continue
    22.       # 循环更新可行解
    23.       while avaliable(slide_win):
    24.           # 找到一个可行解，更新结果值
    25.           rst = update()
    26.           # 缩小窗口
    27.           left += 1

    leetcode

    15：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
    注意：答案中不可以包含重复的三元组。

    1. var threeSum = function(nums) {
    2.   let res = [], len = nums.length, left, right
    3.   if (len < 3) return res
    4.   nums = nums.sort((a, b) => a - b)
    5.   for (let i = 0; i < len; i++) {
    6.       if (nums[i] > 0) break
    7.       if (i > 0 && nums[i] === nums[i - 1]) continue
    8.       left = i + 1
    9.       right = len - 1
    10.       while (left < right) {
    11.           let sum = nums[i] + nums[left] + nums[right]
    12.           if (sum === 0) {
    13.               res.push([nums[i], nums[left], nums[right]])
    14.               while (left < right && nums[left] === nums[left + 1]) left++
    15.               while (left < right && nums[right] === nums[right - 1]) right--
    16.               left++
    17.               right--
    18.           } else if (sum > 0) {
    19.               right--
    20.           } else if (sum < 0) {
    21.               left++
    22.           }
    23.       }
    24.   }
    25.   return res
    26. };