所有奇数长度子数组的和
题目 所有奇数长度子数组的和
思路分析
很容易想到前缀和预处理
主要在于怎么把所有奇数长度框出来
用双指针固定窗口 每轮窗口+=2 这样就能找到所有相差奇数个的r和l
从而使用s[r]-s[l-1]做区间求和
还有个问题在于 这里原数组是从0开始 我们要构造从1开始的前缀和数组
所以有些地方对于模版有所改变
代码实现
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;
}
};
💬 评论