Leetcode # 2845. Count of Interesting Subarrays

Problem

https://leetcode.com/contest/weekly-contest-361/problems/count-of-interesting-subarrays/

相關例題

• Leetcode # 974. ⭐️ Subarray Sums Divisible by K

Solution: Dynamic Programming
[Time Limit Exceeded  609 / 617 testcases passed]

n := len(nums)
cnt(nums[l:r + 1]) := len([True for num in nums[l:r + 1] if num % modulo == k])
(cnt ≡ count)
result := len([True for i in range(n) for j in range(i, n) if cnt(nums[i, j + 1]) % modulo == k])

Time Complexity: O(n ** 2)
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
    n = len(nums)
    satisfied = [1 if num % modulo == k else 0 for num in nums]
    cnt = satisfied.copy()
    result = len([True for count in cnt if count % modulo == k])
    for length in range(2, n + 1):
      for i in range (n - length + 1):
        cnt[i] = cnt[i] + satisfied[i + length - 1]
        if cnt[i] % modulo == k:
          result += 1
        
    return result

Solution

發生 Memory Limit Exceeded 的關係
(# 604 testcase, modulo = 1000000000)
mod_groups 改使用 Counter()

Time Complexity: O(n)
Space Complexity: O(max(n, modulo))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def countInterestingSubarrays(self, nums: List[int], modulo: int, k: int) -> int:
    satisfied = [1 if num % modulo == k else 0 for num in nums]
    
    prefix_mod = result = 0
    mod_groups = Counter({0: 1})
    for s in satisfied:
      prefix_mod = (prefix_mod + s) % modulo
      result += mod_groups[(prefix_mod - k) % modulo]
      mod_groups[prefix_mod] += 1
    return result

Last Updated on 2023/09/10 by A1go