Leetcode 1588所有ODD长度子阵列的总和.C++

Question

我正在通过做一些leetcode问题来练习自己，然而，我不知道为什么这是一个溢出问题。我知道我对子数组求和的方式很糟糕，对子数组的求和有什么建议吗？这个代码的运行时间将永远是

#include <numeric>
class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {
int size = arr.size();//5
int ans = 0;
int sumAll = 0;
int start = 3;
int tempsum;
for(int i =0; i< size; i++){ //sumitself
sumAll += arr[i];
}
ans = sumAll; //alreayd have the 1 index
if(size%2 == 0){//even number 6
int temp = size-1; //5
if(size == 2)
ans = sumAll;
else{
while(start <= temp){//3 < 5
for(int i = 0; i< size; i++){
for(int k =0; k< start; k++){//3
tempsum += arr[i+k];
if(i+k > temp) //reach 5
break;
}
}                  
start+=2;
}
}
ans+= tempsum;
}

else{//odd number 
if(size == 1)
ans = sumAll;
else{
while(start < size){//3
for(int i = 0; i< size; i++){
for(int k =0; k< start; k++){//3
tempsum += arr[i+k];
if(i+k > size) //reach 5
break;
}  
}
start+=2;
}
ans+= tempsum;
ans+= sumAll; //size index
}



}
return ans;
}
};

Answer 1

问题出在arr[i+k]上。i + k的结果可以等于或大于size。你在之后检查它，你已经出界了。

你可能应该修改内环条件，这样就永远不会发生：

for(int k =0; k < start && (i + k) < size; k++){//3

现在你甚至不需要内部检查。

Answer 2

您可以使用前缀和数组技术，然后对于每个索引，您可以使用后缀和数组计算每个奇数长度数组的子数组和。我在LeetCode中提交了以下解决方案，它击败了100%提交的运行时和56.95%的内存使用率

class Solution {
public:
int sumOddLengthSubarrays(vector<int>& arr) {

int n = arr.size();
vector<int> prefix(n+1,0);
int sum = 0;
prefix[1] = arr[0];
for(int i=1;i<n;i++)
prefix[i+1]=(arr[i]+prefix[i]);

for(int i=0;i<n;i++)
{
for(int j=i;j<n;j+=2)
sum+=prefix[j+1]-prefix[i];       
}
return sum;
}
};

Answer 3

https://leetcode.com/problems/sum-of-all-odd-length-subarrays/discuss/1263893/Java-100-one-pass-O(n( -附有解释

class Solution {
public int sumOddLengthSubarrays(int[] arr) {
// alt solution: O(n)
//for each i:
// if(n -1 - i) is odd, then arr[i] is counted (n-1-i)/2 + 1 times, each from 0 to i, total ((n-i)/2+1)*(i+1) times
// if(n -1 - i) is even, then arr[i] is counted (n-1-i)/2 + 1 times, if starting subseq index diff with i is even;
// (n-1-i)/2 times, if starting index diff with i s odd, total (n-i)/2 *(i+1) + (i+1)/2
// if i is even i - 1, i - 3, .. 1, total (i -2)/2 + 1 = i / 2 = (i+1) / 2
// if i is odd i-1, i-3, .., 0 total (i-1)/2 + 1 = (i+1) / 2
int total = 0;
int n = arr.length;
for(int i = 0; i < n; i++)
total += (((n - 1 - i) / 2 + 1) * (i + 1) - ((n-i) % 2)*((i+1) / 2)) * arr[i];
return total;
}
}