Sliding Window At Most Problem
These problems are sliding windows but solve by 2 passes
992. Subarrays with K different Integers
Given an array A
of positive integers, call a (contiguous, not necessarily distinct) subarray of A
good if the number of different integers in that subarray is exactly K
.
(For example, [1,2,3,1,2]
has 3
different integers: 1
, 2
, and 3
.)
Return the number of good subarrays of A
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
return self.atMost(A, K) - self.atMost(A, K-1)
def atMost(self, A, K):
i = 0
record = collections.defaultdict(int)
count = 0
n = len(A)
for j in range(n):
if record[A[j]] == 0:
K-=1
record[A[j]] += 1
while K < 0:
record[A[i]] -=1
if record[A[i]] == 0:
K+=1
i+=1
count += j-i+1
return count
930. Binary Subarrays with Sum
In an array A
of 0
s and 1
s, how many non-empty subarrays have sum S
?
def numSubarraysWithSum(self, A: List[int], S: int) -> int:
return self.atMost(A, S) - self.atMost(A, S-1)
def atMost(self, A, S):
# [0,0,0,0,0], 0
if S < 0: return 0
i = 0
n = len(A)
count = 0
for j in range(n):
S -= A[j]
while S < 0:
S += A[i]
i+=1
count += j-i+1
return count
1248. Count Number of Nice Subarrays
Given an array of integers nums
and an integer k
. A subarray is called nice if there are k
odd numbers on it.
Return the number of nice sub-arrays.
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
return self.atMost(nums, k) - self.atMost(nums, k-1)
def atMost(self, nums, k):
i = 0
count = 0
for j in range(len(nums)):
k -= 1 if nums[j]%2 else 0
while k < 0:
k += 1 if nums[i]%2 else 0
i += 1
count += j-i+1
return count
Last updated
Was this helpful?