[프로그래머스] 연속된 부분 수열의 합 (JS)

풀이 과정

1. 앞에서부터 반복하면서 합 구하기
2. k를 넘은 경우 k보다 큰 동안 시작 요소를 합에서 빼고 시작 인덱스 갱신
3. k가 되는 경우 현재 배열 길이가 현재 결과의 길이보다 짧으면 결과와 결과 배열 길이 갱신

코드

function solution(sequence, k) {
  const result = [0, 0];
  let resultLen = Infinity;
  let [s, e, sum] = [0, 0, 0];
  while (e < sequence.length) {
    sum += sequence[e];
    while (sum > k) sum -= sequence[s++];
    if (sum === k && e - s + 1 < resultLen) {
      [result[0], result[1]] = [s, e];
      resultLen = e - s + 1;
    }
    ++e;
  }
  return result;
}

🦾

처음에 2중 반복문으로 짰다가 당연히 시간 초과로 실패했다.
어떻게 O(n)으로 줄일지 고민하다가 시작과 끝 인덱스를 저장해두는 방법을 선택했는데, 이것도 몇몇 케이스에서 시간 초과가 났다.
문제는 나처럼 합이 k를 초과한 경우 시작 인덱스를 하나 뒤로 미루고 합을 초기화해서 다시 계산을 진행한다면 결국 O(n^2)에 수렴한다는 것이었다.
대신 합이 k를 초과한 경우 시작 인덱스를 뒤로 미루고 현재 합에서 그 값만 빼주면 뒤의 합은 다시 계산을 하지 않아도 된다.
=> 연산을 줄이는 방법을 단순하고 효율적으로 생각하기!