Sliding Window (슬라이딩 윈도우)

Defintion

- This pattern involves creating a window which can either be an array or number from one position to another

- Depending on a certain condition, the window either increases or closes (and a new window is created)

- Very useful for keeping track of a subset of data in an array/string etc.

 

Ex] Write a function called 'maxSubarraySum' which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array. 

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

 

Bad Solution[O(N^2)]

function maxSubArraySum(arr, num) {

  if ( num > arr.length) {

    return null;

  }

 

  var max = -Infinity;

 

  for( let i = 0; i < arr.length - num + 1; i++) {

    temp = 0;

 

    for (let j = 0; j < num; j++) {

      temp += arr[ i + j ];

    } // end of for nested loop j part

 

    if ( temp > max ) {

      max = temp;

    }

 

  } // end of for i part

 

  return max;

}

 

Better Solution [O(N)]

function maxSubArraySum(arr, num){

  let maxSum = 0;

  let tempSum = 0;

  

  if (arr.length < num) {return null;}

 

  // add the first three n numbers

  for(let i = 0; i < num; i++) {

    maxSum += arr[i];

  }

  // 우선 maxSum에 담긴 첫 n의 숫자 더한 것을 tempSum에다 담기

  tempSum = maxSum;

 

  // for문에 돌아가면서 첫 번째 배열 인덱스를 빼고 다음 것을 더하는 식

  for( let i = num; i < arr.length; i++) {

    tempSum = tempSum - arr[i - num] +arr[i];

    maxSum = Math.max(maxSum, tempSum);

  }

  return maxSum;

}