560. Subarray Sum Equals K

문제

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

풀이

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 빈 배열일 땐 합이 0
        int sum = 0;
        int answer = 0;

        for(int n : nums) {
            sum += n;  
            answer += map.getOrDefault(sum-k, 0); // sum-k가 있다면, 부분배열을 만족하므로 그만큼 더해주고
            map.put(sum, map.getOrDefault(sum, 0) + 1); // sum에 해당하는 count를 ++ 
        }
        return answer;      
}
}

• 음수가 포함된 배열의 '정확한' 합을 가지는 SubArray의 개수를 구하는 문제
  • 음수가 포함되었기 때문에 lt를 어떻게 당길지가 애매함
    => 누적합 + HashMap 카운팅 이용 (비양수가 있는 경우, 같은 합이 여러개 존재할 수 있음)
• 현재까지 합이 sum이라면, sum - k가 등장한 인덱스부터 현재 인덱스 i까지가 k를 만족하는 부분배열
  • 예를 들어, [1,1,3,4,5,3,2,-1,-5...]에서 sum - k가 2번 등장했다면, sum - k가 나온 인덱스부터 시작해 부분 배열을 i까지 쭉 이으면, 합이 k인 배열이 등장할 것
  • 그러므로, 현재 sum을 계산한 인덱스 i를 끝으로 가지고, sum - k를 누적합으로 가지는 인덱스+1을 시작으로 가진 부분 배열이 합이 k인 부분 배열이다!
    => map.get(sum -k)가 있다면 sum-k+1이 시작지점인 배열이 존재하는 것이므로 answer에 시작지점의 개수만큼 ++
• Map을 생성할 때 빈 배열일 경우의 합인 0도 초기화해줘야함! map.put(0,1)
  • 합이 0인 prefixSum의 개수 1
  • sum 자체가 k인 경우에도 sum - k로 계산해야하므로, sum - k를 계산할 수 있도록 초기화해주는 것