데이터 구조 및 알고리즘 - 슬라이딩 윈도우 패턴

따라서 여기 있는 것은 인식하고 구현할 수 있는 매우 멋진 패턴입니다. 하위 배열과 관련된 문제가 있을 때마다 항상 이 패턴을 사용하는 것을 고려해야 합니다. 먼저 슬라이딩 윈도우를 사용할 수 있을 때마다 여러 루프와 조건문을 사용하여 무차별 대입할 수도 있습니다. 그래서 당신이 어떤 일을 하고 싶은 상황에서 당신은 당신이 원하는 모든 것을 무차별 대입하는 것을 환영합니다. 더 작은 세트로 작업할 때 이것이 얼마나 오래 걸리는지 결코 깨닫지 못할 것입니다. 반복되는 문자 없이 가장 긴 하위 문자열을 반환하려는 첫 번째 유형의 문제를 살펴보겠습니다. 나는 LeetCode에서 이 문제를 보았고 HackerRank를 믿으며 이 질문에 대한 많은 버전이 있다고 생각합니다. 고전적인 슬라이딩 윈도우 문제입니다. 따라서 숫자 배열의 최대 연속 합을 찾으려는 일반적인 문제를 살펴보겠습니다. 이 메서드는 배열과 배열의 연속 요소인 숫자를 가져옵니다. 다음과 같은 배열이 있다고 가정해 보겠습니다.[10,22,32,13,5,9] 연속 요소를 찾기 위해 전달된 숫자는 3입니다.

무차별 대입 방법을 사용하여 2개의 for 루프를 수행할 수 있으며 다음 배열을 생성하여 합계를 구한 다음 비교할 수 있습니다.

[10,22,32]
[22,32,13]
[32,13,5]
[13,5,9]

그리고 이 접근 방식은 100% 작동하지만 확실히 이 문제를 해결하는 효율적인 방법은 아닙니다. 처음 두 배열을 보면 차이점이 무엇입니까? 첫 번째 배열에서 우리는 10으로 시작하고 두 번째 배열에서는 13으로 끝납니다. 즉, 22와 32가 두 배열 모두에 있다는 의미입니다. 따라서 이 경우 첫 번째 합인 64에서 첫 번째 요소(10)를 빼고 다음 요소(13)를 더하면 됩니다. 64 - 10 + 13, 그러면 67이 되고 새로운 값이 됩니다. 최대값. 이것이 슬라이딩 윈도우의 아이디어입니다. 초기 창에서 시작한 다음 "슬라이드"합니다.

따라서 이 작업을 수행하기 위해 가장 먼저 해야 할 일은 하위 배열의 첫 번째 합계를 구하는 것입니다. 이 경우 간단한 for 루프가 잘 작동합니다. Math.max() 메서드를 사용하고 maxSum을 tempSum(다음 창 요소)과 비교하여 새 합계를 조정해야 하는지 확인하기 위해 tempSum 변수도 만들고 싶습니다. 이제 우리가 해야 할 일은 전달된 연속 번호에서 시작하는 두 번째 루프를 시작하는 것입니다. 이제 새로운 tempSumtempSum - arr[i - num] + arr[i]을 얻고 maxSum보다 크면 저장합니다. 보시다시피 새 배열을 만들지 않고 기본 산술을 사용하여 새 합계를 구하고 비교합니다. 그래서 여기에 대한 나의 최종 기능이 있습니다.

function maxSubarraySum(arr, num) {
    if(num > arr.length) return null;
    let maxSum = 0;
    let tempSum = 0;
    for(let i = 0; i < num; i++) {
        maxSum += arr[i];
    }
    tempSum = maxSum;
    for(let i = num; i < arr.length; i++) {
        tempSum = tempSum - arr[i - num] + arr[i];
        maxSum = Math.max(maxSum, tempSum);
    }

    return maxSum;
}

따라서 모든 유형의 코딩 문제에 대해 항상 가장 먼저 해야 할 일은 내가 첫 번째 줄에서 수행하는 극단적인 경우를 설명하는 것입니다. 그리고 패턴!!!!!!