[演算法筆記] 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: 20
[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
};
findLongestSubstring
Write a function called findLongestSubstring, which accepts a string and returns the length of the longest substring with all distinct characters.
/**
* @param {string} strs
* @return {number}
*/
var findLongestSubstring = function(strs) {}
/**
* Example
* findLongestSubstring('') // 0
* findLongestSubstring('rithmschool') // 7
* findLongestSubstring('thisisawesome') // 6
* findLongestSubstring('thecatinthehat') // 7
* findLongestSubstring('bbbbbb') // 1
* findLongestSubstring('longestsubstring') // 8
* findLongestSubstring('thisishowwedoit') // 6
*/
這是我的面試題啊
function getLengthOfLongestSubstring(str){
let R = 0
let L = 0
let lookup = new Map()
let maxLen = 0
while(R < str.length){
if( lookup.has(str[R]) ){
L = lookup.get(str[R]) + 1
R = lookup.get(str[R]) + 1
lookup.clear()
}
lookup.set(str[R], R)
R ++
maxLen = Math.max(maxLen, R - L)
}
return maxLen
}
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 題可以點這裡
自己在演算法跟資料結構這塊其實還很不足,希望早日能邁向自己期待的樣子