You are given a 0-indexed integer array nums. A subarray of nums is called continuous if:
i, i + 1, ..., j be the indices in the subarray. Then, for each pair of indices i <= 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]. There are 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 <= 1051 <= nums[i] <= 109This approach utilizes a sliding window to find all valid continuous subarrays.
We maintain a window from position 'start' to 'end'. As we iterate over the elements, we adjust the 'start' position to ensure all elements within the window meet the condition 0 <= |nums[i1] - nums[i2]| <= 2. For each position 'end', we extend the window to the right and calculate the number of valid subarrays ending at 'end'.
The function continuous_subarrays computes the total number of continuous subarrays by using two pointers, 'start' and 'end'. For each new element at 'end', it checks the subarrays that end in this position and calculates how many of them are valid by adjusting 'start'.
C
C++
Java
C#
JavaScript
Time Complexity: O(n) because each element is processed at most twice, once by 'start' and once by 'end'.
Space Complexity: O(1) since no additional data structures are used besides basic variables.
A naive solution involves examining all subarrays within the array.
For every possible starting index, calculate every ending index and check if the subarray between these indices forms a continuous subarray. This solution is less efficient but can serve as a baseline check for correctness.
In the function continuousSubarrays, nested loops are used to explore every possible subarray. For each subarray, a check is performed to verify if all elements meet the required continuous condition.
C
C++
Java
Python
C#
Time Complexity: O(n^3) due to triple looping over the array to check all subarrays.
Space Complexity: O(1) as no extra space is used beyond variables.
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: O(n) because each element is processed at most twice, once by 'start' and once by 'end'. Space Complexity: O(1) since no additional data structures are used besides basic variables. |
| Brute Force Approach | Time Complexity: O(n^3) due to triple looping over the array to check all subarrays. Space Complexity: O(1) as no extra space is used beyond variables. |
Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python • NeetCode • 266,725 views views
Watch 9 more video solutions →Practice Continuous Subarrays with our built-in code editor and test cases.
Practice on FleetCode