[001]Subarray Sum Equals K

 

문제: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3307/ 

---

array의 부분합이 K인 구간을 O(N)만에 구하는 알고리즘. 

 

구하고자 하는 것: array[L...R] = K인 구간의 갯수

 

1st.

array[L...R] = K

(=) prefixSum[R] - prefixSum[L-1] = K

(prefixSum은 ∑ array[0...i])

 

2nd. 

prefixSum[R] - prefixSum[L-1] = K 에서 K와 prefixSum[L-1]의 위치를 바꾸면,

(=) prefixSum[R] - K = prefixSum[L-1]이 성립합니다.

 

3rd. 

prefixSum[R]은 ∑ array[0...R]) 이므로 currSum이라는 하나의 변수에 값을 저장할 수 있습니다

그러면 prefixSum[R]의 부분집합인 prefixSum[L-1] 또한 하나의 변수값으로 나타낼 수 있습니다.

 

그러므로, 아래와 같이 식의 형태를 바꿀 수 있습니다.

prefixSum[R] - K = prefixSum[L-1]

(=) currSum - K = variable

 

4th.

그래서 array[L...R] = K인 구간의 갯수를 묻는 문제는,

currSum - K인 variable이 존재하는지 확인하는 문제로 바꿀 수 있습니다.

int variable = currSum - K

(=) int need = currSum - K

 

이런 지점이 존재할 때 마다 카운팅을 해주면 됩니다.

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        
        int currSum = 0;
        int n = nums.size();
        int answer = 0;
        unordered_map<int,int> prefixSum_info;
        
        for (int i = 0; i < n; ++i)
        {
            currSum += nums[i];
            
            if (currSum == k)
                answer += 1;
            
            int need = currSum - k;
            if (prefixSum_info.find(need) != prefixSum_info.end())
                answer += prefixSum_info[need];
            
            prefixSum_info[currSum]++;
        }
        
        
        return answer;
    }
};

---

참고: https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/