Continuous Subarray Sum

0보다 큰 정수만 담긴 벡터와 1보다 큰 정수 k를 받고

해당 정수들의 합으로 k의 배수를 만들 수 있는지 체크 하는 문제

(sum_j - sum_i) % k = 0
=> sum_j % k - sum % k = 0
=> sum_j % k = sum_i % k
Thus for some prefix_sum(0,j) , we need to check if there exist some prefix_sum(0,i) such that both are equal
reference link

위 사항을 몰라 시간 초과가 발생하여 쉽지 않았다.

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        
        int numsSize = nums.size();
        if (numsSize == 1)
        {
            return false;
        }

        vector<int> prefix(numsSize);
        prefix[0] = nums[0] % k;

        unordered_map<int, int> hash{};
        hash[prefix[0]] = 0;
        
        for (int i = 1; i < numsSize; i++)
        {
            prefix[i] = (prefix[i - 1] + nums[i]) % k;
            if (prefix[i] == 0)
            {
                return true;
            }
            else if (0 < hash.count(prefix[i]))
            {
                if (1 < i - hash[prefix[i]])
                {
                    return true;
                }
            }
            else
            {
                hash[prefix[i]] = i;
            }
        }

        return false;
    }
    
};