모든 홀수 길이 하위 배열의 합 O(N) Leetcode #1588.

양의 정수 배열arr이 주어지면 arr의 가능한 모든 홀수 길이 부분 배열의 합을 반환합니다.

A subarray is a contiguous subsequence of the array.

후속 조치:
O(n) 시간 복잡도에서 이 문제를 해결할 수 있습니까?

다음은 무차별 대입 방식에서 Best Case Runtime에 이르는 세 가지 접근 방식입니다.

1. O(N^2 * 로그 n)

var sumOddLengthSubarrays = function(arr) {
    let result = 0;
    for(let i = 0; i < arr.length; i++){
        result += arr[i]
    }

    for(let i = 0; i < arr.length; i++){
        for(let j = i + 2; j < arr.length; j += 2){
            for(let t = i; t <= j; t++){
                result += arr[t];
            }
        }
    }

    return result;
};

2. O(N^2)

var sumOddLengthSubarrays = function(arr) {
    let result = 0;
    let lastWindowSum = 0;
    for(let i = 0; i < arr.length; i++){
        result += arr[i]
    }

    for(let i = 0; i < arr.length; i++){
        for(let j = i + 2; j < arr.length; j += 2){

            // if this is the first time then add current start index to window sum.
            if(lastWindowSum === 0) lastWindowSum = arr[i];

            // memoized sum + next newly added elements only.
            result += lastWindowSum + arr[j] + arr[j - 1];

            // memoize the previous window sum
            lastWindowSum += arr[j] + arr[j - 1];
        }
        // reset last window when new window starts [the position of subarray starts change]
        lastWindowSum = 0;
    }

    return result;
};

3. 오(엔)

O(N) 시간 안에 이 문제를 해결하려면 인덱스에서 만들 수 있는 하위 배열 수를 계산해야 합니다. 그런 다음 2로 나누고 홀수 하위 배열을 얻습니다.

인덱스에 대한 홀수 하위 배열의 수가 있으면 이 인덱스에 하위 배열의 수를 곱하여 현재 인덱스 합계의 최종 결과를 얻을 수 있습니다.

To check how many times a number can appear in a subarray or that how many subarrays can be created with this current number we apply this below formulla.

total occurrances = (currentIndex + 1) * (arrayLength - currentIndex) + 1);

occurrances in only odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2

And to get the sum from the odd arrays we multiply the occurrance with current number.

sum in odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2 * currentNumber.

For JavaScript we have to parseInt - parseInt(((i + 1) * (arr.length - i) + 1) / 2) * arr[i]

var sumOddLengthSubarrays = function(arr) {
    let result = 0;

    for(let i = 0; i < arr.length; ++i) {
        result += parseInt(((i + 1) * (arr.length - i) + 1) / 2) * arr[i];
    }

    return result;
};

Thanks for reading. 🙋‍