파비의 매일매일 공부기록

2023.01.19 Today's Challenge 본문

Problem Solving/LeetCode

2023.01.19 Today's Challenge

fabichoi 2023. 1. 19. 23:45

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

 

Subarray Sums Divisible by K - LeetCode

Subarray Sums Divisible by K - 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

leetcode.com

prefix sum과 frequency table을 활용

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        freq = defaultdict(int)
        freq[0] = 1
        res = pre_sum = 0

        for n in nums:
            pre_sum += n
            rem = pre_sum % k
            res += freq[rem]
            freq[rem] += 1

        return res
반응형

'Problem Solving > LeetCode' 카테고리의 다른 글

2023.01.21 Today's Challenge  (0) 2023.01.21
2023.01.20 Today's Challenge  (0) 2023.01.20
2023.01.18 Today's Challenge  (0) 2023.01.18
2023.01.17 Today's Challenge  (0) 2023.01.17
2023.01.16 Today's Challenge  (0) 2023.01.16
'Problem Solving/LeetCode' Related Articles more
Comments