[LeetCode] 523. Continuous Subarray Sum

https://leetcode.com/problems/continuous-subarray-sum/description/

leetcode - Continuous Subarray Sum

문제 유형 : 부분합, 수학

문제 난이도 : Medium

 

문제

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

• its length is at least two, and
• the sum of the elements of the subarray is a multiple of k.

Note that:

• A subarray is a contiguous part of the array.
• An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

 

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

nums가 좋은 부분배열을 가지면 true를, 아니면 false를 반환하시오.

좋은 부분배열의 조건은, 요소의 개수가 2개 이상이며, 모든 요소의 합이 k의 배수인 것을 말합니다. 0도 포함입니다.

 

풀이

우선, 배열의 값들을 인덱스별로 누적시킨값에 모듈러 k연산을 한 값을 저장시킨다. 만약 그 값이 0이라면, true를 바로 반환시킨다.

위 그림을 보면, 특징을 하나 알 수 있다. 모듈러 k연산을 한 값이 인덱스가 2 이상 차이나면서 같으면, 좋은 부분배열이라는 뜻이다. 나머지값이므로, 그 값만큼 초과한 값이 있다는 건데, 인덱스 2 또는 3은 5를 가지고 있고, 인덱스 0은 5를 가지고 있다.

0부터 2까지의 합 또는, 0부터 3까지의 합에 인덱스 0~0의 수를 빼면, 그 부분배열의 값은 k의 배수라는 것이다.

실제로 인덱스 1~2, 1~3의 합은 6의 배수가 되어 좋은 부분배열이 된다.

 

각 부분합 배열을 1부터 순회하면서, 해시맵에 저장되어있는 나머지 값이 있나 확인한다.

값이 있다면 true를 반환한다.

없으면 부분합[i-1]을 해시맵에 저장시켜서 인덱스 차이가 2이상 나는 값을 저장시킨다.

만약 부분합 배열을 다 순회하고도 없다면, false를 반환하면 된다.

 

코드

C++

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if(n < 2) return false;
        vector<int> prefix_sum(n, 0);
        prefix_sum[0] = nums[0] % k;
        for(int i = 1; i < n; i++) {
            prefix_sum[i] = (prefix_sum[i-1] + nums[i]) % k;
            if(prefix_sum[i] == 0) return true;
        }

        unordered_map<int, bool> mp;

        for(int i = 1; i < n; i++) {
            if(mp[prefix_sum[i]]) return true;
            mp[prefix_sum[i-1]] = true;
        }

        return false;
    }
};