Skip to content

Latest commit

 

History

History
196 lines (143 loc) · 5.64 KB

1588.md

File metadata and controls

196 lines (143 loc) · 5.64 KB
title description keywords
1588. 所有奇数长度子数组的和
LeetCode 1588. 所有奇数长度子数组的和题解，Sum of All Odd Length Subarrays，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
1588. 所有奇数长度子数组的和
所有奇数长度子数组的和
Sum of All Odd Length Subarrays
解题思路
数组
数学
前缀和

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

🟢 Easy  🔖  数组 数学 前缀和  🔗 力扣 LeetCode

题目

Given an array of positive integers arr, return _the sum of all possibleodd-length subarrays of _arr.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: arr = [1,4,2,5,3]

Output: 58

Explanation: The odd-length subarrays of arr and their sums are: [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,2] = 7 [4,2,5] = 11 [2,5,3] = 10 [1,4,2,5,3] = 15

If we add all these together we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Example 2:

Input: arr = [1,2]

Output: 3

Explanation: There are only 2 subarrays of odd length, [1] and [2]. Their sum is 3.

Example 3:

Input: arr = [10,11,12]

Output: 66

Constraints:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000

Follow up:

Could you solve this problem in O(n) time complexity?

题目大意

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

示例 1：

输入： arr = [1,4,2,5,3]

输出： 58

解释： 所有奇数长度子数组和它们的和为： [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,2] = 7 [4,2,5] = 11 [2,5,3] = 10 [1,4,2,5,3] = 15

我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

示例 2：

输入： arr = [1,2]

输出： 3

解释： 总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

示例 3：

输入： arr = [10,11,12]

输出： 66

提示：

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 1000

进阶：

你可以设计一个 O(n) 时间复杂度的算法解决此问题吗？

解题思路

我们可以通过计算每个元素在所有奇数长度子数组中出现的次数，而不是直接找到所有的奇数长度子数组。

假设 arr[i] 出现了 k 次，那么它对总和的贡献就是 arr[i] * k。

  1. 如何计算每个索引的出现次数？

    每个奇数长度的子数组中，当前索引 arr[i] 所在的子数组，必须满足当前索引两侧的元素数量相加为偶数。这意味着，当前索引左侧和右侧的元素个数必须 都为偶数 或 都为奇数。

  2. 计算规律：

    • 我们需要计算以下四种情况：
      • odd_left：从当前索引左侧结束的奇数长度子数组的数量。
      • odd_right：从当前索引右侧开始的奇数长度子数组的数量。
      • even_left：从当前索引左侧结束的偶数长度子数组的数量。
      • even_right：从当前索引右侧开始的偶数长度子数组的数量。
    • 元素 arr[i] 在奇数长度子数组中出现的次数为： odd_left * odd_right + even_left * even_right

  3. 计算公式：

    • 初始化答案 sum = 0。

    • 遍历数组 arr，对于每个索引 i：

    • 从当前索引 i 左侧结束的子数组共有 i + 1 个，其中：

      • 奇数长度子数组的数量为 odd_left = (i + 1) / 2。
      • 偶数长度子数组的数量为 even_left = i / 2 + 1。

    • 从当前索引 i 右侧开始的子数组共有 n - i 个，其中：

      • 奇数长度子数组的数量为 odd_right = (n - i - 1) / 2 + 1。
      • 偶数长度子数组的数量为 even_right = (n - i) / 2。

    • 将 arr[i] 在奇数长度子数组中出现的次数，累加到答案中： sum += arr[i] * (odd_left * odd_right + even_left * even_right)

    • 遍历完所有元素的贡献值后返回总和。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组长度，仅遍历数组一次，每次计算常数次数学公式。
  • 空间复杂度：O(1)，只使用了常数级额外空间。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var sumOddLengthSubarrays = function (arr) {
	const n = arr.length;
	let sum = 0;

	for (let i = 0; i < n; i++) {
		const left = i,
			right = n - i - 1;

		// 计算当前元素对结果的贡献
		const oddCount = (Math.floor(left / 2) + 1) * (Math.floor(right / 2) + 1);
		const evenCount = Math.floor((left + 1) / 2) * Math.floor((right + 1) / 2);

		sum += arr[i] * (oddCount + evenCount);
	}

	return sum;
};

## 相关题目

<!-- prettier-ignore -->
| 题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
| :------: | :------ | :------: | :------ | :------: | :------: |
| 2778 | 特殊元素平方和 |  |  [`数组`](/tag/array.md) [`枚举`](/tag/enumeration.md) | 🟢 | [🀄️](https://leetcode.cn/problems/sum-of-squares-of-special-elements) [🔗](https://leetcode.com/problems/sum-of-squares-of-special-elements) |