[LeetCode] 974. Subarray Sums Divisible by K

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

leetcode - 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.

 

정수배열 nums와 정수 k가 주어진다.

길이가 1이상이며 합이 k의배수인 부분배열의 개수를 구하시오.

 

풀이

부분합으로 값을 누적해서 풀어주면 된다.

https://riveroverflow.tistory.com/entry/LeetCode-523-Continuous-Subarray-Sum

[LeetCode] 523. Continuous Subarray Sum

이 문제와 유사하며,

차이점은 여기서는 요소로 음수가 들어올 수 있어서, 모듈로 연산 값이 음수라면 k를 더해줘야 하고,

위 링크의 문제는 찾기만 하면 되지만, 여기서는 모든 개수를 세야 하므로, 해시맵에 개수를 저장하여 누적시켜야 한다.

그리고, 길이가 1 이상이니 이번에 순회한 요소에 대해 바로 해시맵에 누적시켜주면 된다.

그리고, 나머지가 0인 부분합은 이미 K의 배수이다.

해시맵에 mp[0] = 1로 설정하여 부분합 자기자신만으로 경우의수가 하나 늘어남을 지정한다.

 

코드

C++

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size();
        nums[0] %= k;
        if(nums[0] < 0) nums[0] += k;
        for(int i = 1; i < n; i++) {
            nums[i] = (nums[i] + nums[i-1]) % k;
            if(nums[i] < 0) nums[i] += k;
        }
        int ans = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;
        for(int i = 0; i < n; i++) {
            ans += mp[nums[i]];
            mp[nums[i]]++;
        }

        return ans;
    }
};