Leetcode算法题1501-1600

1501-1510¶

1511-1520¶

1521-1530¶

1531-1540¶

1541-1550¶

1551-1560¶

1561-1570¶

1571-1580¶

1581-1590¶

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

本题有三种接法，复杂度依次减少。

1. 暴力方法

   时间复杂度

   // 暴力
       int sumOddLengthSubarraysOn3(vector<int> &arr) {
           int sum = 0;
         // 遍历所有位置作为起始位置
           for (int i = 0; i < arr.size(); i++) {
             // 设置窗口，因为本题的特殊性，只会选择连续的奇数子集
               for (int step = 1; step + i - 1 < arr.size(); step += 2) {
                 // 累加范围内的子集和
                   sum += accumulate(arr.begin() + i, arr.begin() + i + step, 0);
               }
           }
           return sum;
       }

2. 前缀和方法

   时间复杂度，空间复杂度

   // 前缀和
       int sumOddLengthSubarraysOn2(vector<int> &arr) {
           int sum = 0;
         // 将所有的重复和计算过程利用前缀和将循环变成常数时间复杂度
           vector<int> res = {0};
           for (auto item: arr) {
               res.push_back(item + res.back());
           }
           for (int i = 0; i < arr.size(); i++) {
               for (int step = 1; step + i - 1 < arr.size(); step += 2) {
                   sum += res[i + step] - res[i];
               }
           }
           return sum;
       }

3. 数学法

   时间复杂度为，空间复杂度

   从数学的角度考虑，可以将本题转换为统计任意值arr[i]在奇数子数组中出现次数。

   对于原数组而言，其左边有个数，右边有个数。

   形式化表达为：arr[i]作为某个奇数子数组的成员的充要条件为：其所在奇数子数组左右两边的元素奇偶性相同。即，左侧元素奇数个，右侧元素一定也是奇数个，从而保证加上arr[i]本身总体的奇数个。偶数的情况同样如此。

   因此可以形式化为两种情况：

   • 当元素arr[i]的左右元素个数都是奇数时，在区间中存在方案数为。在区间中存在方案数为。总的可能性即为二者相乘。
   • 当元素arr[i]的左右元素个数都是偶数时，在区间中存在方案数为。在区间中存在方案数为。总的可能性即为二者相乘。

   // 数字法
       int sumOddLengthSubarraysOn1(vector<int> &arr) {
           int sum = 0;
           int n = arr.size();
           int leftCount, rightCount, leftOdd, rightOdd, leftEven, rightEven;
           for (int i = 0; i < n; i++) {
               leftCount = i;
               rightCount = n - i - 1;
               leftOdd = (leftCount + 1) / 2;
               rightOdd = (rightCount + 1) / 2;
               leftEven = leftCount / 2 + 1;
               rightEven = rightCount / 2 + 1;
               sum += arr[i] * (leftOdd * rightOdd + leftEven * rightEven);
           }
           return sum;
       }

1591-1600¶