Portfolio

📄문제

✏️풀이

재영

처음에는 투포인터를 썼다가 틀렸읍니다... 왜냐하면 음수가 있는 줄 몰랐기 때문이었죠.


const subarraySum = function (nums, k) {
  let result = 0;
  let [left, right] = [0, 0];
  let nowSum = nums[0];
  while (left <= right) {
    if (nowSum <= k) {
      if (nowSum === k) result += 1;
      right += 1;
      nowSum += nums[right] ?? 0;
    } else if (nowSum > k) {
      nowSum -= nums[left];
      left += 1;
    }
  }
  return result;
};

그래서! 해시테이블 + 구간 합의 콜라보를 이용했어요.

일단 해시 테이블이니, map을 써보았어요.

일단 이 문제 역시 brute force로 풀기는 뭔가 아쉬웠어요. 따라서 for문 하나로 풀 수 있는 방법을 고민했어요.

그래서 핵심은 구간 합을 사용하자였습니다.

만약에 [1,2,3,4,5] 라는 배열 데이터가 있다고 해봅시다.

그렇다면 현재 3에서 5까지의 합은 어떻게 구할까요?

3 + 4 + 5겠죠?

그런데, 저 3의 위치가, 5의 위치가 일정하지 않다면 어떨까요? 무조건적으로 해당 합을 구할 때마다 for문을 써야 합니다.

그럴 때 우리는 이런 점화식을 쓸 수 있어요.

💡

n-2 에서 n까지의 합은 Sum(0, n) - Sum(0, n -2)이다

즉 구간을 구할 때의 합을 미리 저장해주면서, 이를 계속해서 불러 쓰는 거에요.

그렇다면 우리가 만약 합이 k인 것을 구할 때에는 어떻게 하면 될까요?

우리는 구간 합을 알게 된다면, 다음과 같이 구할 수 있어요.

지금까지 나왔던 구간 합 중에서 현재 구간 합 - k인 것을 찾는다.

있으면 결국에 그만큼 더하면 되는 겁니당.

왜?

[현재 구간 합] - k = [이전 구간 합] < = > [현재 구간 합] - [이전 구간 합] = k이므로.

결과적으로 결과를 리턴합니다!


const subarraySum = function (nums, k) {
  let result = 0; // 결과값
  const map = new Map(); // 해시
  map.set(0, 1); // -> 0을 만드는 경우 수 - 1  = 경우의 수
  nums.reduce((acc, cur) => {
    const now = acc + cur; // sum (구간합)
    const checkNum = now - k; // 점화식에 따른 체크할 값

    if (map.has(checkNum)) {
      result += map.get(checkNum); // 계속해서 경우의 수를 더해줌
    }

    map.set(now, (map.get(now) ?? 0) + 1);

    return now;
  }, 0);
  return result;
};

효성

시간초과 ㅜㅜ


var subarraySum = function(nums, k) {
    let sum = 0, answer = 0;
    for(let i=0; i<nums.length; i++) {
        for(let j=i; j<nums.length; j++) {
            sum += nums[j];
            if(sum === k) {
                answer++;
            }
        }
        sum = 0;
    }
    return answer;
};

참고 풀이


var subarraySum = function(nums, k) {
    let map = new Map();
    let sum = 0;
    let count = 0;
    map.set(0,1);
    for (let i=0;i<nums.length;i++) {
        sum += nums[i];
        if (map.has(sum-k)) count += map.get(sum-k);
        if (map.has(sum)) map.set(sum, map.get(sum)+1);
        else map.set(sum, 1);
    }
    return count;
}

은찬


const subarraySum = (nums, k) => {
    let answer = 0;
    let sum = 0;
    const map = new Map();
    
    map.set(0, 1);
    
    for(let i = 0; i < nums.length; i++){
        sum += nums[i];
        
        if(map.get(sum - k)){
            answer += map.get(sum - k);
        }
        
        map.set(sum, (map.get(sum) ?? 0) + 1);
    }
    
    return answer;
};

Subarray Sum Equals K

📄문제

✏️풀이

시간초과 ㅜㅜ

참고 풀이