---
title: "所有奇数长度子数组的和"
created: 2025-11-28
tags:
  - 算法
---

# 所有奇数长度子数组的和

## 题目 [所有奇数长度子数组的和](https://leetcode.com/problems/sum-of-all-odd-length-subarrays/description/)

![[image-8c28c389.png]]

## 思路分析

很容易想到前缀和预处理

主要在于怎么把所有奇数长度框出来

用双指针固定窗口 每轮窗口+=2 这样就能找到所有相差奇数个的r和l

从而使用s[r]-s[l-1]做区间求和

还有个问题在于 这里原数组是从0开始 我们要构造从1开始的前缀和数组

所以有些地方对于模版有所改变

## 代码实现

```java
class Solution {

public:

    int sumOddLengthSubarrays(vector<int>& arr) {

        const int N=110;

        int s[N];

        int n=arr.size();

        for(int i=1;i<=n;i++){

            //原数组从0存的 要构造从1开始的前缀和数组得加a[i-1]

            s[i]=s[i-1]+arr[i-1];

        }

        int res=0;

        for (int length = 1; length <= n; length += 2) {

            //双指针

            for (int start = 1; start + length -1 <= n; ++start) {

                int end=start+length-1;

                res+=s[end]-s[start-1 ];

            }

        }

        /*

        for (int length = 1; length <= n; length += 2) {

            int start = 1;

            int end = start + length - 1;

            while (end <= n) {

                res += s[end] - s[start - 1];

                start++;

                end = start + length - 1;

            }

         }

        */

        return res;

    }

};
```

## 同类题型

## 视频讲解

---
⬅️ [[尽可能使字符串相等|尽可能使字符串相等]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/双指针相关模型/前后指针/最大价值|最大价值]]