[알고리즘] Slide Window

Silde Window

• 연속된 데이터(주로 배열이나 리스트)에서 일정한 크기의 구간(윈도우)을 움직이며 문제를 해결하는 패턴
• 윈도우의 크기가 고정된 경우와 가변적인 경우가 있습니다.
• 배열이나 문자열 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 유용한 패턴이다

구체적인 예시

연속적인 N개의 원소 합이 target인 경우 중 최소 N 찾기

• Slide Window 적용 해보기
  • 각 경우마다 구간의 합을 구하는 것이 아니라, 특정 구간에 값이 들어오는지 나오는지에 따라 값을 수정함

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minSize = nums.length + 1;
        int tempSum = nums[0];
        int front = 0;
        int back = 0;

        while(front <= back) {
            if (tempSum < target) {
                if (back >= nums.length - 1) {
                    break;
                }
                back++;
                tempSum += nums[back];
            } else if (tempSum >= target) {
                minSize = Math.min(minSize, back - front + 1);
                tempSum -= nums[front];
                front++;
            }
        }

        return minSize;
    }
}

알고리즘 문제 예시

• [ Top Interview 150 ] 209. Minimum Size Subarray Sum
• [ Top Interview 150 ] 3. Longest Substring Without Repeating Characters