Leetcode 1588所有奇数长子数组之和。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)-with-explanation

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;
    }
}