Notes

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: Data Structures

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)\) ). ...