Sliding Window

tags: Sliding Window,OrderedSet Use HashSet to attempt to meet the requirements in the window class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { auto left = 0; auto K = 0; set<long> hset; // set in cpp is an sorted set for (auto right = 0; right < nums.size(); right++) { K = right - left; if (K > k) { hset.erase(nums[left]); left++; } hset.insert(nums[right]); // some numbers are the same. if (hset.size() < (right - left + 1)) { return true; } // abs less than or equal t auto prev = hset.begin(); for (auto iter = hset.begin(); iter != hset.end(); iter++) { if (iter != prev && abs(*prev - *iter) <= t) { return true; } prev = iter; } } return false; } }; // 1. find previous value that meet the requirement, which is abs(nums[i] - nums[j]) <= t // 2. See if also meet the requirement, which is abs(i - j) <= k, otherwise slide left // // Use a fixed window, which size is ~k~. And maintain a set of numbers in the window. // To check if there numbers meet the requirement. It’s too slow and got “Time Limit Exceeded”: https://leetcode.com/submissions/detail/658425251/testcase/. In this case the t is 0, so we can avoid the embed for loop with a if condition: ...

tags: Sliding Window,Hash Table,LeetCode101 This is an “near by” problem that can be solved by Sliding Window. The k in the problem is somehow means contiguous. And using a HashTable to indicate that two values in the different position are equal. The steps is following: Find two values at each side of window are equal. Return true if the offset between their indices is less than or equal k. Otherwise set left to the new position and continue. class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { int left = 0; unordered_map<int, int> indices; for (auto right = 0; right < nums.size(); right++) { auto iter = indices.find(nums[right]); if (iter != indices.end()) { if (abs(right - iter->second) <= k) { return true; } left = iter->second + 1; } indices[nums[right]] = right; } return false; } };

tags: Sliding Window,LeetCode101 Key: sum is greater than or equal to target Compute minimal must above slide left window, as decrease may cause sum less than target. See also 1695. Maximum Erasure Value class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0; int sum = 0; int minimal = INT_MAX; for (auto right = 0; right < nums.size(); right++) { sum += nums[right]; while (sum >= target) { minimal = min(minimal, right - left + 1); sum -= nums[left++]; } } return minimal == INT_MAX ? 0 : minimal; } };

tags: Sliding Window,LeetCode101,Hash Set Key: Fixed size window, right should start from 9 class Solution { public: vector<string> findRepeatedDnaSequences(string s) { int left = 0; unordered_set<string> results; unordered_set<string> hset; for (auto right = 9; right < s.size(); right++) { string sub(s, left, 10); if (hset.find(sub) != hset.end()) { results.insert(sub); } hset.insert(sub); left++; } return vector<string>(results.begin(), results.end()); } };

tags: Sliding Window,LeetCode101,Hash Set Use HashMap to store indices See also: 3. Longest Substring Without Repeating Characters class Solution { public: int maximumUniqueSubarray(vector<int>& nums) { int maximum = 0; int left = 0, right = 0; unordered_map<int, int> indices; for (; right < nums.size(); right++) { int n = nums[right]; if (indices.find(n) != indices.end() && indices[n] + 1 > left) { left = indices[n] + 1; } maximum = max(maximum, std::accumulate(nums.begin() + left, nums.begin() + right + 1, 0)); indices[n] = right; } return maximum; } }; It is too slow, as there is a \(O(n^2)\) time complexity(std::accmulate is the embed \(O(n)\) ). ...

tags: Sliding Window source: Moore, Jordan. “An Introduction to Sliding Window Algorithms.” Medium, July 26, 2020. https://levelup.gitconnected.com/an-introduction-to-sliding-window-algorithms-5533c4fe1cc7. Efficientive algorithm: Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away. – Antoine de Saint-Exupéry The following return values can use a sliding window: Minimum value Maximum value Longest value Shortest value K-sized value And contiguous is one of the biggest clues. Common data structures are strings, arrays and even linked lists. ...

tags: Sliding Window,Brute Force Approach source: GeeksforGeeks. “Window Sliding Technique,” April 16, 2017. https://www.geeksforgeeks.org/window-sliding-technique/. Use a Sliding Window to instead Brute Force Approach, improve time complexity big O from \(O(n^2)\) to \(O(n)\).

tags: Sliding Window,Two Pointers source: 力扣 LeetCode. “题解：借这个问题科普一下「滑动窗口」和「双指针」的区别 - 力扣（LeetCode）.” Accessed March 11, 2022. https://leetcode-cn.com/problems/get-equal-substrings-within-budget/solution/jie-zhe-ge-wen-ti-ke-pu-yi-xia-hua-dong-6128z/. https://stackoverflow.com/a/64078338 Two Pointer to slove the problem of two elements that two pointes pointed. Sliding Window to slove the problem of all elements that in the window.

tags: Sliding Window,LeetCode101,Hash Table Use HashMap to store counts of letters Two points we should be noticed: The length of substring should be (right - left) + 1, as one side must be counted. We must decrese the number in the counts first, and then slide the left window, or we must decrese the wrong one, please compare between Wrong and Correct. Wrong left++; counts[s[left]]--; Correct counts[s[left]]--; left++; The full code see: ...