Problem
You are given an integer array nums and two integers minK and maxK.
A fixed-bound subarray of nums is a subarray that satisfies the following conditions:
The minimum value in the subarray is equal to
minK.The maximum value in the subarray is equal to
maxK.
Return **the *number* of fixed-bound subarrays**.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,3,5,2,7,5], minK = 1, maxK = 5
Output: 2
Explanation: The fixed-bound subarrays are [1,3,5] and [1,3,5,2].
Example 2:
Input: nums = [1,1,1,1], minK = 1, maxK = 1
Output: 10
Explanation: Every subarray of nums is a fixed-bound subarray. There are 10 possible subarrays.
Constraints:
2 <= nums.length <= 1051 <= nums[i], minK, maxK <= 106
Solution
/**
* @param {number[]} nums
* @param {number} minK
* @param {number} maxK
* @return {number}
*/
var countSubarrays = function(nums, minK, maxK) {
var maxNum = 0;
var minNum = 0;
var left = 0;
var res = 0;
var start = 0;
for (var right = 0; right < nums.length; right++) {
if (nums[right] > maxK || nums[right] < minK) {
maxNum = 0;
minNum = 0;
left = right + 1;
start = right + 1;
continue;
}
if (nums[right] === minK) minNum += 1;
if (nums[right] === maxK) maxNum += 1;
while (left < right && (
(nums[left] !== minK && nums[left] !== maxK) ||
(nums[left] === minK && minNum > 1) ||
(nums[left] === maxK && maxNum > 1)
)) {
if (nums[left] === minK) minNum -= 1;
if (nums[left] === maxK) maxNum -= 1;
left += 1;
}
if (minNum >= 1 && maxNum >= 1) {
res += left - start + 1;
}
}
return res;
};
Explain:
Sliding window.
Complexity:
- Time complexity : O(n).
- Space complexity : O(1).