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;
}

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

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！