# Leetcode刷題學習筆記 -- Sliding Window
## Introduction
### sliding window 定義
+ right定義為sliding window裡面的最右邊。
+ left定義為sliding window裡面的最左邊。
+ 根據上面的定義，slding window的長度為 ==right - left + 1==
### left前進條件
### 結束條件
通常會有兩種結束條件的寫法。
```cpp=
// 當left == right, 則length = right - right + 1 = 1
// 也就是window最小長度為1，至少會有一個element在window中。
while(left <= right) {
}
```
另一種結束條件
```cpp=
// 當left == right + 1, 則length = right - right - 1 + 1 = 0
// 也就是window最小長度為0，window可以為empty。
while(left <= right + 1) {
}
```
關於結束條件，可以參考[lee215的解說](https://leetcode.com/problems/replace-the-substring-for-balanced-string/solutions/408978/java-c-python-sliding-window/?orderBy=most_votes)
### Code snippet
```cpp=
for(int left = 0, right = 0; right < size; ++right) {
++m[s[right]]; // 把right加入到window中
while(left <= right + 1 && other_condition) {
--m[s[left++]]; // 把left從window中移除
}
}
```
### Time Complexity
+ time complexity is linear, so it is $O(N)$
## Problems
### [3. Longest Substring Without Repeating Characters(Medium)](https://leetcode.com/problems/longest-substring-without-repeating-characters/)
找出最長的substring(連續的字元)，裡面沒有重複的char。
> 1. 因為要統計沒有重複的字元，且要記錄index所以使用map。
> 2. left為substring的前一個，而不是substring的第一個。
```cpp=
int lengthOfLongestSubstring(string s) {
unordered_map<int, int> m;
auto n = s.length();
int left{-1}, rtn{0};
for(int i = 0; i < n; ++i) {
/* 重複，且比left還後面*/
if(m.count(s[i]) && m[s[i]] > left)
left = m[s[i]];
m[s[i]] = i;
// 每次都update結果，避免最後還需要判斷一次。
rtn = max(rtn, i - left);
}
return rtn;
}
```
2022/06/10
本來是使用sliding windows的概念。但是遇到重複的char的時候，left只能一個一個往前進，比較沒效率。最好的方法是直接跳到重複出現char的下一個位置。因為"abca"已經計算過abc，大小和bca一樣，所以直接跳到a的下一個位置。
```cpp=
int lengthOfLongestSubstring(string s) {
int sz = s.length();
if(sz <= 1) return sz;
int left = 0, right = 0, maxans = 0;
vector<int> alpha(256);
while(right < sz) {
if(alpha[s[right]])
alpha[s[left++]]--;
else
alpha[s[right++]]++;
maxans = max(maxans, right - left);
}
return maxans;
}
```
```cpp=
int lengthOfLongestSubstring(string s) {
int sz = s.length();
// special case, don't need judge
if(sz <= 1) return sz;
vector<int> dict(256, -1);
dict[s[0]] = 0;
int left = 0, maxans = 1;
for(int right = 1; right < sz; ++right) {
if(dict[s[right]] >= left) // 在left的右邊出現過重複的char
left = dict[s[right]] + 1;
dict[s[right]] = right;
maxans = max(maxans, right - left + 1);
}
return maxans;
}
```
time complexity : $O(N)$ 因為只需要走訪一次string
space complexity : $O(1)$ 因為只需要一個固定256的vector來儲存char和idx的對應。
### [567. Permutation in String(Medium)](https://leetcode.com/problems/permutation-in-string/)
有兩個字串s1和s2，找出s2中是否有s1的排列。
> 1. 使用vector統計s1中，所有出現的alphabet的數量。
> 2. 統計s2中和s1相同長度的alphabet數量。
> 3. ==vector長度一樣，則\==會比較每個元素的大小是否一樣。==
```cpp=
bool checkInclusion(string s1, string s2) {
vector<int> m1(26, 0), m2(26, 0);
auto n1 = s1.length();
auto n2 = s2.length();
if(n1 > n2) return false;
for(int i = 0; i < n1; ++i) {
m1[s1[i]-'a']++;
m2[s2[i]-'a']++;
}
if(m1 == m2) return true;
for(int i = n1; i < n2; ++i) {
m2[s2[i]-'a']++;
m2[s2[i - n1]-'a']--;
if(m1 == m2) return true;
}
return false;
}
```
### [713. Subarray Product Less Than K(Medium)](https://leetcode.com/problems/subarray-product-less-than-k/)
給你一個vector<int>，找出subarray的相乘數字小於K。返回subarray的數量。
> 1. subarray表示是連續的element，所以可以使用slide window。用left表示subarray的下標，用right表示subarray的上標。
> 2. right做到哪，就可以得出subarray的數量。所以time complexity為O(N)。
> 3. 當prod >= K，則left必須往前進，直到prod < K，所以使用while。
> 4. 當3在判斷的時候須注意，==left < right==這個條件。
```cpp=
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
if(k == 0) return 0;
int rtn{0}, left{0}, right{0}, prod{1};
while(right < nums.size()) {
prod *= nums[right++];
while(left < right && prod >= k)
prod /= nums[left++];
rtn += right - left;
}
return rtn;
}
```
### [209. Minimum Size Subarray Sum(Medium)](https://leetcode.com/problems/minimum-size-subarray-sum/)
給定一個vector<int>，subarray中相加值大於等於target，返回最小的subarray長度。
> 1. 思考方式和713一樣，因為是subarray所以可以用slide window來思考。
> 2. 當sum(subarray) >= target之後，馬上紀錄是否為最小長度。
> 3. 然後left一直往前移動，直到sum(subarray) < target為止。
```cpp=
int minSubArrayLen(int target, vector<int>& nums) {
auto n = nums.size();
int left{0}, right{0}, rtn{INT_MAX}, sum{0};
while(right < n) {
sum += nums[right++];
while(left < right && sum >= target) {
rtn = min(rtn, right - left);
sum -= nums[left++];
}
}
return rtn == INT_MAX ? 0 : rtn;
}
```
### [487. Max Consecutive Ones II](https://leetcode.com/problems/max-consecutive-ones-ii/)
找出最多的連續1，最多可以翻轉一次0成1。
```
int findMaxConsecutiveOnes(vector<int>& nums) {
int sz = nums.size();
int left = 0, rtn = 0, zeros = 0, k = 1;
for(int right = 0; right < sz; ++right) {
if(nums[right] == 0) ++zeros;
while(zeros > k) {
if(nums[left++] == 0) --zeros;
}
rtn = max(rtn, right - left + 1);
}
return rtn;
}
```
### [424. Longest Repeating Character Replacement](https://leetcode.com/problems/longest-repeating-character-replacement/)
給你一個字串，允許你修改k個char，找出最長的連續重複字串。
> 1. 一開始想到就是用slinding window來計算。
> 2. 假設一個window中由最大出現頻率的char和其他所組成，那修改其他char就會得到最長的Repeating char string。
> 3. 根據上面的假設，
maxf + others = total
total - maxf = others <= k
因為剩下的char不能大於k
> 4. 為什麼不用更新maxf ?
當找到一個答案的時候，如果有下一個比目前答案還要長的字串，勢必新的maxf一定會大於之前的。
> 5. total也可以用right - left + 1來取代。
```cpp=
int characterReplacement(string s, int k) {
int maxans = 0, maxf = 0;
int left = 0, total = 0;
int sz = s.size();
vector<int> st(26);
for(int right = 0; right < sz; ++right) {
maxf = max(maxf, ++st[s[right] - 'A']);
total++;
if(total - maxf <= k)
maxans = max(maxans, right - left + 1);
else {
--st[s[left++] - 'A'];
total--;
}
}
// time : O(N)
// space : O(1)
return maxans;
}
```
### [1712. Ways to Split Array Into Three Subarrays](https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/description/)
給你一個vector<int> nums, 我要把vector分成三個subarray。且必須滿足 1st subarray sum <= 2nd subarray sum。2nd subarray sum <= 3rd subarray sum。滿足這樣的條件的subarray切法有幾種?
> 1. 因為是求subarray sum所以使用prefix sum
> 2. i : 代表1st subarray的右邊界，因為subarray不能為空，所以 i<= sz - 3;
> 3. j : 代表2nd subaary的右邊界，且滿足1st sum <= 2nd sum
> 4. k : 代表2nd subaary的右邊界，且不滿足2nd sum <= 3rd sum。
> 5. 使用 j = max(j, i + 1) 是因為j 不用從i + 1開始找，從上次j繼續往後找。
```cpp
class Solution {
// 1, 2, 2, 2, 5, 0
// 1, 3, 5, 7, 12, 12
// i j/k
// <--> <------> <--> // j, k是second subarray的右邊界範圍
// j/k <= sz - 2
// i <= sz - 3
// pfs[i] --> first subarray sum, j the last index of first array
// pfs[j/k] - pfs[i] --> second subarray sum, k the last index of first array
// pfs[sz - 1] - pfs[j/k] -- > third subarray sum
public:
int waysToSplit(vector<int>& nums) {
int sz = nums.size();
partial_sum(nums.begin(), nums.end(), nums.begin());
int rtn{0}, mod = 1e9 + 7;
for(int i = 0, j = 0, k = 0; i <= sz - 3; ++i) {
j = max(j, i + 1); // 從之前的j繼續往後找
// j往後移動，直到 2nd sum >= 1st sum
while(j <= sz - 2 && nums[j] - nums[i] < nums[i]) ++j;
k = max(k, j); // 從之前的k繼續往後找
// k往後移動，直到 3rd sum >= 2nd sum不成立
while(k <= sz - 2 && nums[sz - 1] - nums[k] >= nums[k] - nums[i]) ++k;
rtn += k - j;
rtn %= mod;
}
return rtn;
}
};
```
### [1838. Frequency of the Most Frequest Element](https://leetcode.com/problems/frequency-of-the-most-frequent-element/description)
> 1. 因為數字只能往上加，不能往下遞減。所以只能對齊比自己大的數字。
> 2. 先進行排序
> 3. 針對每個數字，看看比他還小的數字中，有幾個可以對齊上來。假設有(right - left + 1)個數字對齊到nums[right]，則這數的綜合是
```(right - left + 1) * nums[right]```
> 4. 使用cur來記錄目前right - left + 1中的數字總和
> 5. 如果(right - left + 1) * nums[right] > cur + k，表示把k加到這些數字也湊不到這麼長一樣的nums[right]，所以left向前進。
```cpp=
class Solution {
public:
int maxFrequency(vector<int>& nums, int k) {
int left = 0, ans = 1;
long cur = 0;
sort(begin(nums), end(nums)); //O(NlogN)
for(int right = 0; right < nums.size(); ++right) { // O(N)
cur += nums[right];
while((long)(right - left + 1) * nums[right] > cur + k)
cur -= nums[left++];
ans = max(ans, right - left + 1);
}
return ans;
// time : O(NlogN + N) = O(NlogN)
// space : O(1)
}
};
```
###### tags: `leetcode` `刷題`
Sign in with Wallet
Connect another wallet