Leetcode # 974. ⭐️ Subarray Sums Divisible by K

2023.09.10
★★ Medium LeetCode Modulo Prefix Sum Subarray Sums Divisible by K

Problem

https://leetcode.com/problems/subarray-sums-divisible-by-k

Solution

令 nums[i] = [4, 5, 0, -2, -3, 1], k = 5

能夠被k整除的子字串有：
[5], [0], [5, 0], [-2, -3], [0, -2, -3], [5, 0, -2, -3], [4, 5, 0, -2, -3, 1]

sum(nums[:i + 1]) % k == sum(nums[:j + 1]) % k, i < j
⇔ sum(nums[i + 1: j + 1]) % k == 0

注意點

C/C++, Java, C# 等程式語言
模除後的餘數符號(正負)與被除數相同¹
（即被除數為負，餘數也會為負）
故 prefix_mod = (prefix_mod + num % k + k) % k

Time Complexity: O(len(nums))
Space Complexity: O(k)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def subarraysDivByK(self, nums: List[int], k: int) -> int:
    prefix_mod = result = 0
    mod_groups = [1] + [0] * (k - 1)
    for num in nums:
      # (prefix_mod + num) % k
      # = (prefix_mod % k + num % k) % k
      # = (prefix_mod + num % k) % k
      prefix_mod = (prefix_mod + num % k) % k
      result += mod_groups[prefix_mod]
      mod_groups[prefix_mod] += 1
    return result

Last Updated on 2024/06/10 by A1go

References

1
參考模除｜剰余演算｜Modulo