연속된 부분 수열의 합, JavaScript

문제

https://school.programmers.co.kr/learn/courses/30/lessons/178870?language=javascript#

오답

테스트 통과는 가능하지만, 시간 초과가 심각하다.

function solution(sequence, k) {
    let result = [];
    
    // 우선 합 값을 찾아라.
    // 연속해야 한다.
    // 가장 짧은 배열이여야만한다.
    let tmp = 0;
    let tmpArray = [];
        
    for(let i = 0; i < sequence.length; i++){
        for(let j = 0; j <= sequence.length; j++){
            if(sequence.slice(i, j).reduce((acc, cur) => acc + cur, 0) === k){
                tmpArray.push(sequence.slice(i, j));
            }
        }
    }
    // console.log(tmpArray);
    let flag = tmpArray.sort((a, b) => a.length - b.length);
    // console.log(flag[0]);
    
    let startIndex = flag[0][0];
    let lastIndex = flag[0][flag[0].length-1];
    // console.log("start", startIndex);
    // console.log("last", lastIndex);
    
    if(startIndex === lastIndex){
        if(flag[0].length === 1){
            result.push(sequence.indexOf(startIndex));
            result.push(sequence.indexOf(lastIndex));         
            return result;
        }
        result.push(sequence.indexOf(startIndex));
        result.push(flag[0].length-1);
        // console.log("같은 경우", result);
        return result;
    }
    
    result.push(sequence.indexOf(startIndex));
    result.push(sequence.indexOf(lastIndex));
    // console.log(result);
    
    return result;
}

정답

while문을 통해 시작값부터 끝값까지 가면서 sum을 구하고 이를 k의 값과 비교해 같아질 때 까지 진행합니다.
(endIndex < sequence.length)를 통해 시작값과 끝값을 통해 sum을 계속해서 구하고 기존의 result값과 비교해 짧은 값을 구하고 요구사항에 맞춰, start, end를 뽑아내면 됩니다.

function solution(sequence, k) {
  let startIndex = 0;
  let endIndex = 0;
  let sum = sequence[0];
  let result = null;

  while (startIndex <= endIndex && endIndex < sequence.length) {
    if (sum === k) {
      if (result === null || endIndex - startIndex < result[1] - result[0]) {
        result = [startIndex, endIndex];
      }
      sum -= sequence[startIndex];
      startIndex++;
    } else if (sum < k) {
      endIndex++;
      sum += sequence[endIndex];
    } else {
      sum -= sequence[startIndex];
      startIndex++;
    }
  }

  return result;
}