✔️ 3. Sliding Window

1. 한 위치에서 다른 위치로 이동 할 수 있는 window(고정된 사이즈-특정 범위)를 생성, 내부 요소의 값을 이용하는 패턴
   • window : 단일 변수, 하위 배열 또는 필요한 경우 다른 문자열도 될 수 있음
   • 이동은 보통 왼쪽에서 오른쪽, 즉 요소의 시작 위치, 또는 배열이나 문자열의 시작 위치에서 끝나는 위치로 이동
2. 특정 조건에 따라 window는 증가하거나 닫히거나 새로 생성 될 수 있다
3. 배열과 문자열에서 데이터의 하위 집합을 추적하는데 유용함
4. 투 포인터와 비슷한 부분이 있다

💻 예제 1

정수 배열과 n이라는 숫자를 받아
해당 배열에서 n만큼 연속된 요소의 합의 최대값을 계산하는 maxSubArraySum이라는 함수를 작성하시오.

maxSubArraySum([1,2,5,2,8,1,5],2) // 10
maxSubArraySum([1,2,5,2,8,1,5],4) // 17
maxSubArraySum([4,2,1,6],1) //6
maxSubArraySum([4,2,1,6,2],4) // 13
maxSubArraySum([],4) // null

🔎 내가 했던 풀이

🔸 풀이 전 어떻게 구성할지 생각해봤다

1. 빈 배열 또는 조건에 맞지 않을 경우 null을 리턴한다 -> 배열의 길이보다 n의 숫자가 클때
2. 결과 값으로 쓸 result와 비교를 위해 임시로 비교를 위한 temp 변수 선언
3. temp변수에 첫 비교 값인 n-1 인덱스까지의 값의 합(처음부터 n개 요소의 합) 할당
4. window는 고정값이므로 한칸씩 이동하므로 이전 첫 요소 빼고 다음 요소 더함 (하나의 인덱스만큼 이동하며 n개의 합을 유지한다) => 그리고 temp 값과 result를 비교해서 둘 중 큰 숫자를 result에 할당한다.
   • for문의 시작은 n부터 시작(배열의 인덱스는 0부터 시작하므로)
   • 배열 모두 비교 후 끝나면 비교하며 저장된 가장 큰 합의 값인 result를 할당한다.

const maxSubarraySum = (arr, n) => {
  if (arr.length < n) return null;

  let result = 0;
  let temp = 0;

  for (let i = 0; i < n; i++) { 
    result += arr[i];
  }

  temp = result;

  for (let j = n; j < arr.length; j++) {
    temp = temp - arr[j - n] + arr[j];
    result = Math.max(result, temp);
  }

  return result;
};

🔎 해답

위 풀이와 동일 시간 복잡도는 O(N)