974. Subarray Sums Divisible by K.md

974. Subarray Sums Divisible by K (Medium)

[tag] prefix sum, two pointers, dict/hashtable

• use 2 prefix sum and a hashtable/dict {prefix sum % k: count} and then same as two sum
• need to consider the reminder of negitive value, so (reminder + k) to transfer it to positive.

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        sum1 = 0
        num_dict = defaultdict(int)
        num_dict[0] = 1
        ans = 0
        for i, num in enumerate(nums):
            sum1 += num
            sum1_reminder = sum1 % k
            # prevent the negitive values
            sum2_reminder = (k +  sum1_reminder) % k
            if sum2_reminder in num_dict:
                ans += num_dict[sum2_reminder]
            num_dict[sum1_reminder] += 1
        return ans