[LeetCode] 974. Subarray Sums Divisible by K

974. Subarray Sums Divisible by K

Medium

Given an integer array nums and an integer k, return the number of non-empty subarrays that have a sum divisible by k.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [4,5,0,-2,-3,1], k = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by k = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Example 2:

Input: nums = [5], k = 9
Output: 0

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

---

문제 풀이

• k 와 배열이 주어졌을때, k 로 나눠질 수 있는 부분 배열의 갯수를 구하자
• 제한 사항을 보면 3 * 10^4 이기 때문에, 브루트 폴스로 풀기 힘들것 같다.
• 해쉬 테이블을 사용하여 연속으로 더 해진 부분집합의 값을 저장하면서 부분 배열을 찾자.
  • 우선, 모듈러 공식을 적어보면 nums[i : j] % k == 0 일때 우리는 원하는 값을 얻게 된다. 
  • nums 라고 적은 부분은 sum 생략했고 i ~ j 사이의 배열 값의 합이다. 
  • 배열의 범위를 쪼개보자, (nums[ : j] - nums[ : i]) % k == 0 이 식을 다시 정리하면,
  • nums[ : j] % k == nums[ : i] % k 가 된다. 
  • 즉, 배열의 부분 배열 i ~ j 의 합이 k 로 나눴을때 0 이 되는 조건을 만족할때, 
  • nums[ : j] % k == nums[ : i] % k 도 만족하게 된다. 
  • 즉 현재 위치 j 까지 더해진 총합을 k 로 나머지 계산 한것을 딕셔너리에 계속 저장하고,
  • 그 다음 j 에서 k 로 나머지 처리한 값이 딕셔너리에 존재한다면,
  • 딕셔너리에 들어있는 i 부터 현재 j 까지의 부분 배열은 k 로 모듈러 계산 했을때 0 이 된다. 
    • 예를 들어, 4, 5, 0, -2, -3 있을때, 딕셔너리에는 
    • {(0, 1), (4, 3), (2: 1)} 이 들어있다. (0, 1) 은 초기값으로 넣어 맨 앞 변수를 하나만 선택했을때나 한자리 변수를 선택할때 참고 된다. 
    • 여기서 (4, 3) 은 각각 4, 5, 0 자리에서 이전 까지의 배열 값을 더하고 k 값 5 로 나머지 처리해 줬을때 생기는 변수이다. 
    • 즉 (5, 0, -2, -3), (0, -2, -3), (-2, -3) 이 세개를 딕셔너리를 참고해서 답에 더해 줄 수 있다.

소스 코드

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        hash_table = defaultdict(int)
        hash_table[0] = 1
        total, ans = 0, 0
        for i in nums:
            total += i
            temp = total % k
            if temp in hash_table:
                ans += hash_table[temp]
            hash_table[temp] += 1
            
        return ans