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

深藏阁楼爱情的钟 2022-12-10 14:42 94阅读 0赞

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

输入：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

法一：暴力法，时间复杂度为O（n3)：

class Solution { 
    public:
        int sumOddLengthSubarrays(vector<int>& arr) { 
            int res = 0;
            for (int i = 0; i < arr.size(); ++i) {     // i为计算连续数组和的起点
                for (int sz = 1; sz + i <= arr.size(); sz += 2) { 
                    res += accumulate(arr.begin() + i, arr.begin() + i + sz, 0);
                }
            }
    
            return res;
        }
    };

法二：使用前缀和数组，前缀和即前n个数字的和，可以用一个数组保存下来前1、2、······、n个数字的和，之后每次计算一个连续子数组的和时，只需要用O（1）的时间即可，即如果想计算下标为2、3、4的子数组的和，只需用4的前缀和减去1的前缀和即可。前缀和数组需要O（n）的空间，而计算子数组和的时间从O（n）下降到了O（1），因此总时间复杂度为O（n2)：

class Solution { 
    public:
        int sumOddLengthSubarrays(vector<int>& arr) { 
            int res = 0;
            vector<int> prefixSum = { 0};
    
            for (int i : arr) { 
            	prefixSum.push_back(prefixSum.back() + i);
    		}
    		
            for (int i = 0; i < arr.size(); ++i) {     // i是子数组计算的起点
                for (int sz = 1; sz + i <= arr.size(); sz += 2) {     // sz为子数组的大小
                    res += prefixSum[sz + i] - prefixSum[i];
                }
            }
    
            return res;
        }
    };

法三：遍历一遍数组，每遍历到一个元素，计算出该元素会出现在几个奇数长度的子数组中，就知道了此元素在结果中会被计算多少次。当一个元素左边有连续偶（奇）数个元素时，它右边必须也有连续偶（奇）数个元素，这样加上此元素，子数组的元素数量才是奇数（以下谈到该元素左边或右边的元素数量时都包含该元素，并且元素数为0也算偶数个元素）：  
1.当该元素左边元素数量为left时，左边连续偶数个元素的情况有`(left + 1) / 2`种，左边连续奇数个元素的情况有`left / 2`种。  
2.当该元素右边元素数量为right时，右边连续偶数个元素的情况有`(right + 1) / 2`种，右边连续奇数个元素的情况有`right / 2`种。

在找以上规律时，由于整数除法结果会截去小数位，因此可能会有两个可能的公式，如某元素左边有2个元素时，它左边只可能有一种连续偶数个元素的情况，左边连续偶数个元素的情况的公式就可以是`left/2`或`(left+1)/2`；如果该元素左边有3个元素，它左边只可能有两种连续偶数个元素的情况，此时左边连续偶数个元素的情况的公式是`(left+1)/2`或`(left+2)/2`，取交集就是`(left+1)/2`。其余公式同理。

此种方法每遍历到一个元素时，计算它在结果中出现的次数的时间复杂度为O（1），且只需遍历一次数组即可，因此总时间复杂度为O（n），空间复杂度为O（1）：

class Solution { 
    public:
        int sumOddLengthSubarrays(vector<int>& arr) { 
            int res = 0;
            
            for (int i = 0; i < arr.size(); ++i) { 
                int left = i + 1, right = arr.size() - i;
                int left_odd = left / 2;
                int left_even = (left + 1) / 2;
                int right_odd = right / 2;
                int right_even = (right + 1) / 2;
            
                res += (left_odd * right_odd + left_even * right_even) * arr[i];
            }
    
            return res;
        }
    };