[LeetCode] 560. Subarray Sum Equals K

https://leetcode.com/problems/subarray-sum-equals-k/

Subarray Sum Equals K - LeetCode

Subarray Sum Equals K - Medium

 

배열에서 연속된 부분배열의 합이 k가 되는 부분배열의 개수를 구하는 문제다.

 

nums[i]를 nums[i] + nums[i-1]로 갱신해주자.

그러면 nums[i]는 0~i까지의 합으로 바뀐다.

이때 배열 j~i까지의 합을 구하기 위해서는 nums[i]-nums[j-1]을 구하면 된다.

이를 이용하자.

 

map m을 하나 만들어 m[0]=1로 초기화해주고 (아무것도 더해지지 않은 상태.)

nums[i]를 만들때마다 m[nums[i]-k]의 개수를 찾아준다.

m[nums[i]-k]가 있다면 이 앞의 j 인덱스에 nums[i]-nums[j] = k를 만족시키는. 즉, 문제의 조건을 만족시키는 부분배열이 있다는 뜻이다.

m[nums[i]-k]를 결과에 더해주고

m[nums[i]]를 ++ 해주자.

 

전체 풀이 코드

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ret = 0;
        unordered_map<int, int> m;
        m[0] = 1;
        for (int i=0; i<nums.size(); i++) {
            if (i) nums[i] += nums[i-1];
            ret += m[nums[i]-k];
            m[nums[i]]++;
        }
        return ret;
    }
};