算法和数据结构面试题(JavaScript+Python)——滑动窗口

1,426 阅读7分钟

适用情况:

input是一些线性结构如链表,数组,字符串等,求最长/最短子字符串或是某些特定的长度要求 滑动窗口避免了重复循环元素,在计算sum等数值时适应,但是有些情况必须遍历所有值解题就不适用了。

模式

res = []
<1.设置窗口> 
start= 0
end= 0
while end < len(arr):
	<2.执行计算 (window.add(arr[end]))>
	end += 1start
	if/while (<3设置条件:满足start指针移动>):
		<4.执行计算 (window.remove(arr[start]))>
		start += 1
	<5.更新res:注意判断在循环内外更新的情况>

细节

  1. window的数据类型,easy一般为数值、数组,用于加减求和等,medium的一般为哈希表(字典),用来统计元素的数量。主要看题目要求
  2. 更新res的时候注意判断,res是否包含while条件的情况,包含则在while内更新,不包含则在while外更新。一般用min、max对比更新

例题1 固定长度求字串最大总和(easy)

固定窗口 给定一个正数数组和一个正数'k',找到大小为'k'的任何连续子数组的最大和。 例: Input: [2, 1, 5, 1, 3, 2], k=3 Output: 9 Explanation: Subarray with maximum sum is [5, 1, 3].

解题思路:

  1. 设置window:windowStart、windowEnd(在for循环中设置,小于输入列表的长度)、windowSum(窗口在一个位置上的结果,比如要求和)、result(列表用来存结果)
  2. 进入windoEnd的循环for,在窗口内进行执行计算(如windowSum加和)
  3. 设置窗口移动的条件if,满足时移动窗口 3.1 移动前获取当前结果(如把前面得出的当前结果存入列表,或max比较大小) 3.2 执行计算改变当前结果(如windowSum减去最前面的值) 3.3 改变windowStart移动窗口
  4. 获得返回值

JS

const max_sub_array_of_size_k = function(k, arr) {
  // TODO: Write your code here
  let sumArr = [],
  windowStart = 0,
  windowSum = 0;
  for (let windowEnd = 0; windowEnd < arr.length; windowEnd ++){  //end是小于数组长度,不能等于
  	//<执行计算(windowEnd)>
    windowSum += arr[windowEnd];
    if (windowEnd >= k-1){       //是大于等于的时候才移动,不是小于
      //maxSum = Math.max(maxSum, windowSum);也可以直接在循环里面找最大 
      //<修改result>
      sumArr.push(windowSum);
      //<执行计算(windowStart)>
      windowSum -= arr[windowStart];
      windowStart += 1;
    }
  }
  maxSum = Math.max.apply(null,sumArr)
  return maxSum;
};

语法笔记:max里的参数不能是数组,所以要借用call/apply(Object, args) ,当Object为null时this指向改为window。而apply的参数要数组,call的参数不能为数组

Python

def max_sub_array_of_size_k(k, arr):
  max_sum , window_sum = 0, 0
  window_start = 0

  for window_end in range(len(arr)):
    window_sum += arr[window_end]  # add the next element
    # slide the window, we don't need to slide if we've not hit the required window size of 'k'
    if window_end >= k-1:
      max_sum = max(max_sum, window_sum)
      window_sum -= arr[window_start]  # subtract the element going out
      window_start += 1  # slide the window ahead
  return max_sum

例题2 给定总和的最短字串(easy)

缩放窗口移动双指针 给定一个正数数组和一个正数'S',找到其和大于或等于'S'的最小连续子数组的长度。如果不存在此类子数组,则返回0。 例: Input: [2, 1, 5, 2, 3, 2], S=7 Output: 2 Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].

滑动窗口算法的思路是这样:

1、我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right]称为一个「窗口」。

2、我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。

3、此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。

4、重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

解题思路:第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动

作者:labuladong 链接:leetcode-cn.com/problems/mi…

JS

const smallest_subarray_with_given_sum = function(s, arr) {
  let windowStart = 0,
  windowSum = 0,
  minLen = Infinity; //求最小值时设初始值为Infinity

  for (let windowEnd = 0; windowEnd <= arr.length-1; windowEnd++){  //windowEnd可以是小于数组长度,或者小于等于数组长度-1,记住窗口的概念图
  	//<执行计算(windowEnd)>
    windowSum += arr[windowEnd];
    while(windowSum >= s){
      //<修改result>
      minLen = Math.min(minLen, windowEnd - windowStart + 1);
      //<执行计算(windowStart)>tart
      windowSum -= arr[windowStart];
      windowStart += 1;
    }
  }

  if (minLen === Infinity){   //不要忘了没有符合条件的substring情况
    minLen = 0;
  }
  return minLen;
};

Python

import math


def smallest_subarray_with_given_sum(s, arr):
  window_sum = 0
  min_length = math.inf
  window_start = 0

  for window_end in range(0, len(arr)):
    window_sum += arr[window_end]  # add the next element
    # shrink the window as small as possible until the 'window_sum' is smaller than 's'
    while window_sum >= s:
      min_length = min(min_length, window_end - window_start + 1)
      window_sum -= arr[window_start]
      window_start += 1
  if min_length == math.inf:
    return 0
  return min_length

例题3 固定字母数的最长字串(medium)

更复杂的<执行计算>步骤,用哈希表记录字母频率 给定一个字符串,找出其字母不超过K个的最长子串 例: Input: String="araaci", K=2 Output: 4 Explanation: The longest substring with no more than '2' distinct characters is "araa".

解题思路:这道题升了一个level主要是因为<执行计算>这一步骤更复杂,需要创建哈希表记录字母频率,哈希表在py中即字典,在js中即对象,就是带有键值对的数据结构。另外要注意代码中的两个特殊情况。

function longest_substring_with_k_distinct (str, k) {
  let windowStart = 0,
  maxLen = 0,
  charFrequency = {};
  for (let windowEnd = 0; windowEnd < str.length; windowEnd++){
    //<执行计算(windowEnd)>在对象charFrequency内创建字母属性,用属性的值记录字母频率
    const rightChar = str[windowEnd];
    if (!(rightChar in charFrequency)){ //特殊情况,如果charFrequency对象内没有rightChar则创建一个新的属性,值为0
      charFrequency[rightChar] = 0;
    }
    charFrequency[rightChar] += 1;  //给这个属性的值加一,计数

    while (Object.keys(charFrequency).length > k){ 
    //<执行计算(windowStart)>修改对象(哈希表)内的字母属性值
      const leftChar = str[windowStart];
      charFrequency[leftChar] -= 1;  //移动窗口时给这个属性的值减一,表示去掉一个字母
      if (charFrequency[leftChar] === 0){  //特殊情况,如果这个属性的值为零,即这个字母在对象中不存在,删去
        delete charFrequency[leftChar];
      }
      windowStart += 1;    
    }
    //<改变result> 在while循环外面改,因为不能包含字母数量大于k的情况
    maxLen = Math.max(maxLen, windowEnd - windowStart + 1);
  }
  return maxLen;
}

语法笔记:获取对象属性个数用 Object.keys(obj).length

def longest_substring_with_k_distinct(str, k):
  windowStart = 0
  charFreq = {}
  charLen = 0
  for windowEnd in range(len(str)):  #注意range不包括最后一项,这里不用减一
    rightChar = str[windowEnd]
    if rightChar not in charFreq:
      charFreq[rightChar] = 0
    charFreq[rightChar] += 1

    while len(charFreq) > k:
      leftChar = str[windowStart]
      charFreq[leftChar] -= 1      #这个字母计数减一
      if charFreq[leftChar] == 0:
        del charFreq[leftChar]
      windowStart += 1
    charLen = max(charLen, windowEnd - windowStart + 1) #注意这一步要在for循环里面

  return charLen

例题四 无重复字符的最长子串

leetcode 3(medium) 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

解题思路:

  1. 总体跟框架走窗口、window.add(end)、条件、window.remove(start)、更新
  2. 细节: window设为字典,end++并统计窗口内的字母频率,freq大于1则移动start 更新res要在循环外
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s: return 0
        res = 0
        charFreq = {}
        # <1.设置窗口>
        start, end = 0, 0
        while end < len(s):
            # <2.执行计算 (window.add(arr[end]))>
            endChar = s[end]
            # 简便写法,判断字母是否在字典中,若为新字母则创建一个新键并赋值为0,再加1计数
            # 不要写成charFreq.get(endChar, "0"),这里的0表示字符串,不能加减
            charFreq[endChar] = charFreq.get(endChar, 0) + 1 
            end += 1
            
            # <3.设置条件>
            # 满足指针移动的条件是end对应字母是否重复出现
            # 因为有for循环,每次都会判断字典中end指针对应字母的数值,所以只要判断当前这个字母即可
            while charFreq[endChar] > 1:
                # <4.执行计算 (window.remove(arr[start]))>
                startChar = s[start]
                charFreq[startChar] = charFreq.get(startChar) - 1
                if charFreq[startChar] == 0:
                    del charFreq[startChar]
                start += 1

            # <5.更新res>
            # 第一次出错,把res更新写在while循环里面。
            # 判断方法:charFreq[endChar] > 1这个条件是否符合输出的情况,
            # 要求的是不含有重复字符,即charFreq[endChar] > 1的情况下不能更新res,要把这个情况处理完才能更新
            res = max(res, len(charFreq))
        return res

参考资料:

Grokking the Coding Interview: Patterns for Coding Questions

labuladong的算法小抄