Leetcode—1588.所有奇数长度子数组的和【简单】

2023每日刷题（十九）

Leetcode—1588.所有奇数长度子数组的和

在这里插入图片描述

直接法实现代码



int sumOddLengthSubarrays(int* arr, int arrSize){
    int i = 1;
    int sum = 0;
    int left = 0, right;
    int k;
    int j = 0;
    while(i <= arrSize) {
        for(left = 0; left < arrSize; left++) {
            right = left + i;
            k = left;
            if(right <= arrSize) {
                while(k < right) {
                    sum += arr[k++];
                }
            } else {
                break;
            }
        }
        j++;
        i = 2 * j + 1;
    }
    return sum;
}

运行结果

在这里插入图片描述

枚举法实现代码



int sumOddLengthSubarrays(int* arr, int arrSize){
    int ans = 0, sum;
    for(int i = 0; i < arrSize; i++) {
        for(int j = i; j < arrSize; j++) {
            if((j - i + 1) % 2 == 1) {
                sum = 0;
                for(int k = i; k <= j; k++) {
                    sum += arr[k];
                }
                ans += sum;
            }
        }
    }
    return ans;
}

运行结果

在这里插入图片描述
时间复杂度 $O(n^3)$ ，空间复杂度 $O (1)$

改进的实现代码



int sumOddLengthSubarrays(int* arr, int arrSize){
    int ans = 0, sum;
    for(int i = 0; i < arrSize; i++) {
        sum = 0;
        for(int j = i; j < arrSize; j++) {
            sum += arr[j];
            if((j - i + 1) % 2 == 1) {
                ans += sum;
            }
        }
    }
    return ans;
}

时间复杂度 $O(n^2)$ ，空间复杂度 $O (1)$

运行结果

在这里插入图片描述

前缀和实现代码



int sumOddLengthSubarrays(int* arr, int arrSize){
    int *preSum = (int *)malloc(sizeof(int) * (arrSize + 1));
    preSum[0] = 0;
    for(int i = 0; i < arrSize; i++) {
        preSum[i + 1] = preSum[i] + arr[i];
    }
    int ans = 0;
    for(int i = 0; i < arrSize; i++) {
        for(int j = i; j < arrSize; j++) {
            if((j - i + 1) % 2 == 1) {
                ans += preSum[j + 1] - preSum[i];
            }
        }
    }
    free(preSum);
    return ans;
}