【算法】1588. 所有奇数长度子数组的和(多语言实现)

举报
二当家的白帽子 发表于 2022/09/01 11:41:19 2022/09/01
【摘要】 1588. 所有奇数长度子数组的和:给你一个正整数数组 arr ,请你计算所有可能的奇数长度子数组的和。子数组 定义为原数组中的一个连续子序列。请你返回 arr 中 所有奇数长度子数组的和 。 样例 1输入: arr = [1,4,2,5,3] 输出: 58 解释: 所有奇数长度子数组和它们的和为: [1] = 1 [4] = 4 [2] = 2 [5] = 5 [3] = 3 [1,4,...

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

给你一个正整数数组 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(n3)的解法应该都能想到。
  • 有人会想到用滑动窗口或者前缀和,这些是常用的优化手段。
  • 根据题意我们知道子数组就像子序列,是否出现在子数组中,和数字具体是多少无关,只和位置有关。
  • 既然和具体数字无关,这种子序列,子数组,排列组合,就一定有规律,可以用数学的方式去解决。
  • 我们可以一头到尾遍历一遍,然后累加 每个数字的值乘以每个数字出现在子数组的次数 就可以得到结果。接下来就变成我们是否可以找到每个数字出现在子数组中的次数规律。
  • 假设我们选定一个数字,那么除了这个数字之外,我们还可以另外选择 偶数个其他数字 凑成奇数长度的子数组。
  • 我们可以把其他数字的选择,分成左面和右面两部分,那么这个选定的数字出现在子数组的次数就是 左面可选数字方案数 * 右面数字可选方案数
  • 奇数=1 + 偶数,选定一个数字之后,如果左面选择奇数个数字,那么右面也必须选择奇数个数字;如果左面选择偶数个数字,那么右面也要选择偶数个数字。这样加上选定的数字,就刚好是奇数长度子数组。
  • 最终每个数字出现的次数就是 左面选择奇数个数字的方案数 * 右面选择奇数个数字的方案数 + 左面选择偶数个数字的方案数 * 右面选择偶数个数字的方案数
  • 从0到n中,奇数的数量是(n + 1) / 2个,偶数的数量是n / 2 + 1(0也算偶数个)。

题解

java

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int ans = 0;

        int endIndex = arr.length - 1;
        for (int i = 0; i <= endIndex; ++i) {
            int leftCount  = i;
            int rightCount = endIndex - i;
            int leftOdd    = (leftCount + 1) / 2;
            int rightOdd   = (rightCount + 1) / 2;
            int leftEven   = leftCount / 2 + 1;
            int rightEven  = rightCount / 2 + 1;
            ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
        }

        return ans;
    }
}

c

int sumOddLengthSubarrays(int* arr, int arrSize){
    int ans = 0;

    int endIndex = arrSize - 1;
    for (int i = 0; i <= endIndex; i++) {
        int leftCount = i;
        int rightCount = endIndex - i;
        int leftOdd = (leftCount + 1) / 2;
        int rightOdd = (rightCount + 1) / 2;
        int leftEven = leftCount / 2 + 1;
        int rightEven = rightCount / 2 + 1;
        ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
    }

    return ans;
}

c++

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int ans = 0;

        int endIndex = arr.size() - 1;
        for (int i = 0; i <= endIndex; i++) {
            int leftCount = i;
            int rightCount = endIndex - i;
            int leftOdd = (leftCount + 1) / 2;
            int rightOdd = (rightCount + 1) / 2;
            int leftEven = leftCount / 2 + 1;
            int rightEven = rightCount / 2 + 1;
            ans += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
        }

        return ans;
    }
};

python

class Solution:
    def sumOddLengthSubarrays(self, arr: List[int]) -> int:
        ans = 0
        endIndex = len(arr) - 1
        for i, v in enumerate(arr):
            leftCount, rightCount = i, endIndex - i
            leftOdd = (leftCount + 1) // 2
            rightOdd = (rightCount + 1) // 2
            leftEven = leftCount // 2 + 1
            rightEven = rightCount // 2 + 1
            ans += v * (leftOdd * rightOdd + leftEven * rightEven)
        return ans
        

go

func sumOddLengthSubarrays(arr []int) (ans int) {
	endIndex := len(arr) - 1
	for i, v := range arr {
		leftCount, rightCount := i, endIndex-i
		leftOdd := (leftCount + 1) / 2
		rightOdd := (rightCount + 1) / 2
		leftEven := leftCount/2 + 1
		rightEven := rightCount/2 + 1
		ans += v * (leftOdd*rightOdd + leftEven*rightEven)
	}
	return ans
}

rust

impl Solution {
    pub fn sum_odd_length_subarrays(arr: Vec<i32>) -> i32 {
        let endIndex = arr.len() - 1;
        arr.iter().enumerate().map(|(i, v)| {
            let leftCount = i;
            let rightCount = endIndex - i;
            let leftOdd = (leftCount + 1) / 2;
            let rightOdd = (rightCount + 1) / 2;
            let leftEven = leftCount / 2 + 1;
            let rightEven = rightCount / 2 + 1;
            arr[i] * ((leftOdd * rightOdd + leftEven * rightEven) as i32)
        }).sum()
    }
}

原题传送门:https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://bbs.huaweicloud.com/community/usersnew/id_1628396583336561 博客原创~


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。