[演算法筆記] Sliding window
資料內有一個滿足特定條件長度的窗口 (make a subarray “valid”)，可以藉由滑動此窗口來取得想要的資料
演算法系列文
[Array & String]
- Sliding window
- Two Pointer & Prefix sum
適用情境
- 線性資料結構 eg array, string …
- 答案是連續的資料
- 出現以下字樣 Minimum or maximum length, Number of subarrays/substrings, Max or minimum sum
題目 key words
Find the {valid subarray} in {some way}
{valid subarray}:滿足特定條件
{some way} eg 最大 / 最長 / 計算數量
- Find the longest subarray with a sum less than or equal to
k - Find the longest substring that has at most one
"0" - Find the number of subarrays that have a product less than
k - Find the sum of the subarray with the largest sum whose length is
k
Concept of Sliding window
資料內有一個滿足特定條件長度的窗口 (make a subarray “valid”)，可以藉由滑動此窗口來取得想要的資料
Sliding window 使用 L 跟 R 兩個 pointer 移動找出符合條件的 subarray。
subarray?
用圖片來說比較快，以 [1,2,3] 來說，他的 subarray 就有以下六種，只要連續且包含在 [1,2,3] 裡的就是 subarray
換句話來說，所有 subarrays 都可以根據 L 跟 R 移動位置拿到
[1, 2, 3]
[1] // L=0, R=0
[1,2] // L=0, R=1
[1,2,3] // L=0, R=2
[2] // L=1, R=1
[2,3] // L=1, R=2
[3] // L=2, R=2使用這種方式解題好處是效能會比一般迴圈好非常多，以 Find the sum of the subarray with the largest sum whose length is target 這個題目來說，一般迴圈每次都要重覆算五次，但 Sliding window 只需要移除前一個值並加上後面的值即可
nums = [1,2,3,4,5,6,7], target 5
// general 迴圈兩次
[1,2,3,4,5] // sum: 15
[2,3,4,5,6] // sum: 15
[3,4,5,6,7] // sum: 25
// Sliding window 迴圈一次
[1,2,3,4,5] // sum: 15
15 - 1 + 6 // sum: 20
20 - 2 + 7 // sum: 25一樣的題目一般迴圈時間複雜度為 𝑂(𝑛2)，但使用 Sliding window 時間複雜度變 O(n)
Leetcode 題
列一些常見的 sliding window，希望自己之後看到這些類似題目可以很順利的解出來
Find the length of the longest subarray that has a sum less than or equal to target
/**
* @param {number} target
* @param {number[]} nums
* @return {number}
*/
var LogestSubArrayLen = function(target, nums) {}
/**
* Example 1
* Input: target = 5, nums = [3,2,1,3,1,1]
* Output: 3
* Example 2
* Input: target = 5, nums = [1,1,1]
* Output: 3
*/
使用 L 跟 R 兩個 pointer 移動找出符合條件的 subarray
- 當 subarray is valid 那就 R++
- 若不符合那就 L++，並移除前一個值後繼續步驟 1
var LogestSubArrayLen = function(target, nums) {
let L = 0;
let R = 0
let sum = 0
let longest = 0
while(R < nums.length){
sum += nums[R]
while(sum > k){
sum -= nums[L]
L++
}
longest = Math.max(longest, R - L + 1)
R++;
}
return longest
};
LogestSubArrayLen([3, 2, 1, 3, 1, 1] , 5)雖然解答有兩個 while 但其實他並不會重覆運算，時間複雜度為 O(n)，同樣題目使用一般 loop 時間複雜度為 𝑂(𝑛2)，效能好非常多
Given an array of positive integers nums and an integer target, return the number of subarrays where the product of all the elements in the subarray is strictly less than target.
Number of subarrays (713. Subarray Product Less Than K)
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numSubarrayProductLessThanK = function(nums, k) {};
/**
* Example 1
* Input: nums = [10,5,2,6], k = 100
* Output: 8
* Example 2
* Input: nums = [1,2,3], k = 0
* Output: 0
*/
使用 L 跟 R 兩個 pointer 移動找出相乘小於 k 的 subarray 數量
- 當 subarray is valid 那就 R++
- 若不符合那就 L++，並移除前一個值後繼續步驟 1
var numSubarrayProductLessThanK = function(nums, k) {
if (k <= 1) return 0;
let L = 0;
let R = 0
let product = 1
let count = 0
while(R < nums.length){
product *= nums[R]
while(product >= k){
product /= nums[L]
L++
}
count += (R - L + 1)
R++;
}
return count
};Given an integer array nums and an integer target, find the sum of the subarray with the largest sum whose length is target
Fixed window size
前兩題 window size 是 dynamic，這題會有固定 window size
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findBestSubarray = function(nums, k) {}
/**
* Example 1
* Input: nums = [3,-1,4,12,-8,5,6], k = 4
* Output: 18
*/
使用 L 跟 R 兩個 pointer 移動，找出數量為 k 的連續 subarrays 當中加總最大值
- 第一次會算 k 次
- 因為每次算量固定，所以第二次之後的每次運算只要減掉前一個值跟加下一個值就好
var findBestSubarray = function(nums, k) {
let L = 0;
let R = k
let logestSum = 0
let singleSum = 0
// first count
for(let i=0; i<R; i++){
singleSum += nums[i]
}
logestSum = singleSum
while(R < nums.length){
singleSum = singleSum - nums[L++] + nums[R++]
logestSum = Math.max(logestSum, singleSum)
}
return logestSum
};
findBestSubarray([3, -1, 4, 12, -8, 5, 6], 4)Sliding window 相關 Leetcode 題可以點這裡
自己在演算法跟資料結構這塊其實還很不足，希望早日能邁向自己期待的樣子
