LeetCode 560 - Subarray Sum Equals K (Medium)

문제

LeetCode - 560번

풀이 과정

특정 구간의 합이 k 이 되는 총 개수를 구하는 문제입니다.

원래 투 포인터 를 사용해서 구하려고 했는데 음수가 존재하기 때문에 올바른 값을 구할 수 없었습니다.
따라서 1차원 배열에 누적 합을 계속 기록하면서 계산을 수행합니다.
여기서 합이 k 가 되는 구간을 찾기 위해서는 다음과 같이 생각해볼 수 있습니다.

a, b, ... e, f ...

만약 f 까지의 합이 30이고 우리가 찾는 k = 20 일 때 a ~ f 까지 숫자 중에서 합이 10 인 지점을 찾으면 됩니다.
그 이유는 a ~ b = 10 이라면 c ~ f 의 구간이 30 - 10 = 20 이 되기 때문입니다. (구간 합 알고리즘)

코드

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  let answer = 0,
    acc = 0;
  const prefix = new Map();
  prefix.set(0, 1);

  for (const num of nums) {
    acc += num;
    if (prefix.has(acc - k)) {
      answer += prefix.get(acc - k);
    }

    if (prefix.has(acc)) {
      prefix.set(acc, prefix.get(acc) + 1);
    } else {
      prefix.set(acc, 1);
    }
  }

  return answer;
};