Notice
250x250
Recent Posts
Recent Comments
Link
넘치게 채우기
[LeetCode] 974. Subarray Sums Divisible by K 본문
728x90
반응형
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
이 문제와 유사하며,
차이점은 여기서는 요소로 음수가 들어올 수 있어서, 모듈로 연산 값이 음수라면 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;
}
};
728x90
반응형
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 1122. Relative Sort Array (0) | 2024.06.11 |
---|---|
[LeetCode] 1051. Height Checker (0) | 2024.06.10 |
[LeetCode] 523. Continuous Subarray Sum (0) | 2024.06.08 |
[LeetCode] 648. Replace Words (0) | 2024.06.07 |
[LeetCode] 846. Hand of Straights (0) | 2024.06.06 |