Leetcode - 560. Subarray Sum Equals K

문제

주어진 배열의 sub-array의 합이 k가 되는 모든 sub-array갯수는?

Input: nums = [1,1,1], k = 2
Output: 2

Input: nums = [1,2,3], k = 3
Output: 2

Input: nums = [7,-7,7,-7,7], k = 7
Output: 6

Input: nums = [4,3,-1,-2,3], k = 7
Output: 2

해결 아이디어

 +-----+--------+
 0     i        j

• sum[i, j) 는 기본적으로 sum[0, j) - sum[0, i) 로 구할 수 있다.
• 배열을 순회하면서 누적합(sum[0, j)) 을 계산하다가 sum[0, j) - k 값이 이전에도 등장했다면 sum[0, j) - k 등장했던 횟수를 count 변수에 누적하여 더한다.
• 배열을 모두 순회하면 count값이 최종 정답.
• 이해하는데 어려움이 많았던 솔루션..(해설 참고함)

풀이

• 해시테이블에 누적합(sum[0, j)) 값이 등장한 빈도(frequency)를 기록한다.
• sum[0, j) - k 값이 해시테이블에 존재한다면 해당 빈도수를 cnt에 누적하여 더한다.
• 해시테이블에 0 을 1로 미리 만들어 놓고 순회해야하는 이유
  처음으로sum[0, j) - k 이 0이 되는 경우가 합이 k가 되는경우이므로 +1 해야하기 때문.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        int cur_sum = 0;
        int cnt = 0;
        
        freq[0]++; // for case of (cur_sum - k == 0)
        for (int i = 0; i < nums.size(); i++) {
            cur_sum += nums[i];
            
            if (freq.find(cur_sum - k) != freq.end()) {
                cnt += freq[cur_sum - k];
            }
            freq[cur_sum]++;
        }
        return cnt;
    }
};