LeetCode 560. Subarray Sum Equals K (C++)

The link : leetcode.com/problems/subarray-sum-equals-k/

Subarray Sum Equals K - LeetCode

 

 

문제에 친절하게도 힌트가 주어져있었고, 힌트 덕분에 풀 수 있었다.

 

문제 풀이는 다음과 같다. 

1. key가 int, value가 int인 맵을 구현한다.

2. 맵의 [0] = 1로 저장해둔다. 두 연속된 배열의 차가 0이거나, 배열의 원소가 1개인 값이 k인 경우를 고려해서 넣는 값이다. 이 부분이 이해가 안되더라도 아래 코드와 예시를 보면 이해할 수 있다.

3. 배열의 사이즈만큼 for문을 돌린다. 이때 코드는 아래와 같다.

        for(int i=0; i<nums.size(); i++){
            sum += nums[i];
            if(m.find(sum-k)!=m.end()) ans+=m[sum-k];
            m[sum]++;
        }

4. 배열의 원소를 모두 더해준다. 만약 배열의 원소가 배열 = [1,3]이고 k=4일때, 첫 번째 원소 1의 경우에는 sum(1-4) = -3의 값이 존재하지 않는다. 때문에 if문은 스킵해주고 m[1]++이 진행된다. 이때 m[1]++의 뜻은, 1의 key값이 +1개 존재한다는 의미이다.

5. 다음 원소인 3을 봐보자. m[4-4] = m[0] = 1로, 답이 1만큼 존재함을 뜻한다. 때문에 ans += m[sum-k]를 해주면 된다.

 

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