[Leetcode] Sliding Window Summary
2021-01-26 09:13
Example 3:
Input: A = [2,-1,2], K = 3
Output: 3
Note:
1-10 ^ 51
Everything is the same, except with negative integer(s) in the array
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/discuss/143726/C%2B%2BJavaPython-O(N)-Using-Deque
Q: Why keep the deque increase?
A: If B[i] d.back(), it means that compared with d.back(),
B[i] can help us make the subarray length shorter and sum bigger. So no need to keep d.back() in our deque.
More detailed on this, we always add at the LAST position
B[d.back] B[future id] - B[d.back()] >= k && B[d.back()] >= B[i]
B[future id] - B[i] >= k too
so no need to keep B[d.back()]
What is the purpose of second while loop?
To keep B[D[i]] increasing in the deque.
Why keep the deque increase?
If B[i] and moreover we already know that i > d.back(), it means that compared with d.back(),B[i] can help us make the subarray length shorter and sum bigger. So no need to keep d.back() in our deque.
1 int shortestSubarray(vectorint> A, int K) { 2 int N = A.size(), res = N + 1; 3 dequeint> d; 4 for (int i = 0; i ) { 5 if (i > 0) 6 A[i] += A[i - 1]; 7 if (A[i] >= K) 8 res = min(res, i + 1); 9 while (d.size() > 0 && A[i] - A[d.front()] >= K) 10 res = min(res, i - d.front()), d.pop_front(); 11 while (d.size() > 0 && A[i] A[d.back()]) 12 d.pop_back(); 13 d.push_back(i); 14 } 15 return res 1; 16 }
https://leetcode.com/problems/minimum-window-substring/
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
Note:
- If there is no such window in S that covers all characters in T, return the empty string
"". - If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
Variation 1:
1 class Solution { 2 public: 3 string minWindow(string s, string t) { 4 unordered_mapchar, int> m; 5 for (char c : t) { 6 m[c]++; 7 } 8 int sz = m.size(); 9 string res; 10 for (int i = 0, j = 0, cnt = 0; i i) { 11 if (m[s[i]] == 1) 12 cnt++; 13 m[s[i]]--; 14 while (m[s[j]] 0) { 15 m[s[j++]]++; 16 } 17 18 if (cnt == sz) { 19 if (res.empty() || res.size() > i - j + 1) 20 res = s.substr(j, i - j + 1); 21 } 22 } 23 return res; 24 } 25 };
Variation 2:
1 class Solution { 2 public: 3 string minWindow(string s, string t) { 4 vectorint> v(128, 0); 5 for (char c : t) 6 v[c]++; 7 int start = 0, end = 0, head = 0, counter = t.size (), len = INT_MAX; 8 while (end s.size ()) 9 { 10 if (v[s[end++]]-- > 0) counter--; 11 while (counter == 0) 12 { 13 if (end - start len) 14 { 15 len = end - start; 16 head = start; 17 } 18 if (v[s[start++]]++ == 0) counter++; 19 } 20 } 21 return len == INT_MAX ? "" : s.substr (head, len); 22 } 23 };
文章标题：[Leetcode] Sliding Window Summary
文章链接：http://soscw.com/index.php/essay/47202.html