Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]
Solution: Sliding Window w/ Two Pointers & Set
Maintain a sliding window of unique numbers with maximum size of k.
We can store the numbers in the window in a hashset.
When we move the right pointer up, move the left pointer up until:
- all numbers in the window are unique
- the window size
<= k
Time Complexity: O(n) 246ms
Space Complexity: O(k) 71.5MB
var maximumSubarraySum = function(nums, k) {
let set = new Set(), sum = 0;
let ans = 0, n = nums.length;
for (let j = 0, i = 0; j < n; j++) {
sum += nums[j];
while (set.has(nums[j]) || j - i >= k) {
sum -= nums[i];
set.delete(nums[i]);
i++;
}
set.add(nums[j]);
if (j - i + 1 === k) ans = Math.max(ans, sum);
}
return ans;
};
Comments
Post a Comment