[ 자바스크립트(JavaScript) ] section05 - 4 - 연속 부분수열2

📍 section05 - 4 - 연속 부분수열2

연속 부분수열1보다 약간 더 어려운 문제였다. 이전 문제는 다음 rt 포인터가 기준보다 커지면 arr[lt++]처리를 해줬는데, 이 문제는 특정 기준 값 이하인 경우 새로운 숫자가 포함된 연속 부분 수열을 구해주면 된다. 그럼 이전 숫자는 안 구하는지 궁금할 수 있는데, 이전 숫자가 끝에 있으면서 연속 수열인 값은 이전 과정에서 구했기 때문에, 새로운 경우의 수만 누적해주면 된다.

 

1. 반복문을 따라 sum+=arr[rt]를 누적한다.
2. 만약, sum>target이면 sum<=target이 될 때까지 sum을 빼준다.(lt)
3. 마지막에 부분 수열이 몇 개 있는지 계산해주면 된다. (경우의 수를 구할 때는 rt-lt+1을 해주면 된다.)

 

 

 

728x90

 

 

let n = 5;
let target = 5;
let arr = [1, 3, 1, 2, 3];

console.log(solution(n, target, arr));

function solution(n, target, arr) {
  let lt = sum = ans = 0;

  for (let rt = 0; rt < n; rt++) {
    sum += arr[rt];

    while (sum > target) {
      sum -= arr[lt++];
    }
    ans += rt - lt + 1;
  }
  return ans;
}