2762. Continuous Subarrays
Description
You are given a 0-indexed integer array nums
. A subarray of nums
is called continuous if:
- Let
i
,i + 1
, ...,j
be the indices in the subarray. Then, for each pair of indicesi <= i1, i2 <= j
,0 <= |nums[i1] - nums[i2]| <= 2
.
Return the total number of continuous subarrays.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [5,4,2,4] Output: 8 Explanation: Continuous subarray of size 1: [5], [4], [2], [4]. Continuous subarray of size 2: [5,4], [4,2], [2,4]. Continuous subarray of size 3: [4,2,4]. Thereare no subarrys of size 4. Total continuous subarrays = 4 + 3 + 1 = 8. It can be shown that there are no more continuous subarrays.
Example 2:
Input: nums = [1,2,3] Output: 6 Explanation: Continuous subarray of size 1: [1], [2], [3]. Continuous subarray of size 2: [1,2], [2,3]. Continuous subarray of size 3: [1,2,3]. Total continuous subarrays = 3 + 2 + 1 = 6.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
Solutions
Solution 1: Ordered List + Two Pointers
We can use two pointers, $i$ and $j$, to maintain the left and right endpoints of the current subarray, and use an ordered list to maintain all elements in the current subarray.
Iterate through the array $nums$. For the current number $nums[i]$ we're iterating over, we add it to the ordered list. If the difference between the maximum and minimum values in the ordered list is greater than $2$, we then loop to move the pointer $i$ to the right, continuously removing $nums[i]$ from the ordered list, until the list is empty or the maximum difference between elements in the ordered list is not greater than $2$. At this point, the number of uninterrupted subarrays is $j - i + 1$, which we add to the answer.
After the iteration, return the answer.
The time complexity is $O(n \times \log n)$ and the space complexity is $O(n)$, where $n$ is the length of the array $nums$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|