1248. Count Number of Nice Subarrays #259
-
Topics: Given an array of integers Return the number of nice sub-arrays. Example 1:
Example 2:
Example 3:
Constraints:
Hint:
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
The problem requires finding the number of subarrays in an integer array Key Points:
Approach:The problem can be solved using the sliding window technique combined with prefix sums. The main idea is to efficiently track the number of odd numbers within a moving subarray and count the valid subarrays. Plan:
Let's implement this solution in PHP: 1248. Count Number of Nice Subarrays <?php
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function numberOfSubarrays($nums, $k) {
$r = array(0, 0);
$res = 0;
$pre = 0;
$cur = 0;
for($i = 0; $i < count($nums); $i++){
$r[$nums[$i] & 1]++;
if($r[1] == $k){
$pre = $cur;
}
while($r[1] == $k){
$r[$nums[$cur] & 1]--;
$cur++;
}
$res += $cur - $pre;
}
return $res;
}
// Example usage:
$nums = [1,1,2,1,1];
$k = 3;
echo numberOfSubarrays($nums, $k) . "\n"; // Output: 2
$nums = [2,4,6];
$k = 1;
echo numberOfSubarrays($nums, $k) . "\n"; // Output: 0
$nums = [2,2,2,1,2,2,1,2,2,2];
$k = 2;
echo numberOfSubarrays($nums, $k) . "\n"; // Output: 16
?> Explanation:We iterate through the array while maintaining the following:
Example Walkthrough:Example 1:Input:
Example 2:Input:
Example 3:Input:
Time Complexity:
Space Complexity:
Output for Examples:
The sliding window with prefix sums efficiently counts the number of "nice" subarrays. This approach is optimal for handling large arrays due to its linear time complexity. |
Beta Was this translation helpful? Give feedback.
The problem requires finding the number of subarrays in an integer array
nums
that contain exactlyk
odd numbers. Subarrays are contiguous, and we need to optimize for performance due to constraints on the size of the array.Key Points:
num % 2 != 0
or using bitwise operationnum & 1
.Approach:
The pr…