跳至主要內容

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

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

🟢   🔖  数组 数学 前缀和  🔗 力扣open in new window LeetCodeopen in new window

题目

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) |
Copyright © 2024 2xiao