연속부분수열1

• 강의 듣기 전 내 풀이

const solution = (target, arr) => {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    let sum = arr[i];
    for (let j = i + 1; j < arr.length; j++) {
      sum += arr[j];
      if (sum > target) break;
      if (sum == target) {
        count++;
        break;
      }
    }
  }
  // 이렇게 짜버리면 O(n*n)
  return count;
};

const result = solution(6, [1, 2, 1, 3, 1, 1, 1, 2]);
console.log(result);

• 강의 반영한 풀이

const solution = (target, arr) => {
  let count = 0;
  let leftPointer = 0;
  let sum = 0;
  const limit = arr.length;
  for (let rightPointer = 0; rightPointer < limit; rightPointer++) {
    sum += arr[rightPointer];
    if (sum == target) count++;
    while (sum >= target) {
      sum -= arr[leftPointer++];
      if (sum == target) count++;
    }
  } // 사실상 O(n)
  return count;
};

const result = solution(6, [1, 2, 1, 3, 1, 1, 1, 2]);
console.log(result);