五月训练 Day8

• • 0. Leetcode [51480. 一维数组的动态和](https://leetcode-cn.com/problems/running-sum-of-1d-array/)
  • • 分析与解答
  • 1. Leetcode [1588. 所有奇数长度子数组的和](https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays/)
  • • 分析与解答
  • 2. Leetcode [1442. 形成两个异或相等数组的三元组数目](https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/)
  • • 分析与解答
  • 3. Leetcode [1094. 拼车](https://leetcode-cn.com/problems/car-pooling/)
  • • 分析与解答
  • 总结

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。

前缀和的基本形态。直接迭代计算 s u m [ i ] = s u m [ i − 1 ] + n u m [ i ] sum[i] = sum[i - 1] + num[i] sum[i]=sum[i−1]+num[i] 即可

class Solution {
public:
    vector runningSum(vector& nums) {
        vector result;
        result.resize(nums.size(), 0);
        result[0] = nums[0]; // nums.length >= 1
        for (int i = 1; i < nums.size(); ++i) {
            result[i] = nums[i] + result[i - 1];
        }
        
        return result;
    }
};

算法时间复杂度为 O ( N ) O(N) O(N)

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。

通过前缀和计算 s u m [ i , j ] sum[i, j] sum[i,j]，之后搜索所有奇数数组和：

class Solution {
public:
    int sumOddLengthSubarrays(vector& arr) {
        vector sumN;
        sumN.resize(arr.size(), 0);
        sumN[0] = arr[0];
        for (int i = 1; i < arr.size(); ++i) { // 构造前缀和
            sumN[i] = sumN[i - 1] + arr[i];
        }
        
        int result(0);
        for (int n = 1; n <= arr.size(); n += 2) { // 对所有 n 循环
            for (int j = n - 1; j < sumN.size(); ++j) {
                if (j - n >= 0) { // 计算当前 n 下所有可能的子字符串
                    result += sumN[j] - sumN[j - n];
                } else {
                    result += sumN[j];
                }
            }
        }

        return result;
    }
};

算法时间复杂度为 O ( N 2 ) O(N^2) O(N2)。可以通过数学方法实现 O ( N ) O(N) O(N) 算法。

给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ … ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

构造异或形式的前缀和，只要找到区间元素异或为 0 0 0 的区间 [ i , k ] [i, k] [i,k]，就可在其中任意选择 i < j ≤ k i < j le k i

class Solution {
public:
    int countTriplets(vector& arr) {
        vector xorN;
        xorN.resize(arr.size(), 0);
        xorN[0] = arr[0]; // 1 <= arr.length
        for (int i = 1; i < arr.size(); ++i) { // 构造前缀和
            xorN[i] = xorN[i - 1] ^ arr[i];
        }

        int result(0);
        // [i, k] 中异或为 0，则有 j，使 xor[i, j] == xor[j, k], 且 j 的数量为 k - i
        for (int i = 0; i < arr.size() - 1; ++i) {
            for (int k = i + 1; k < arr.size(); ++k) { // 固定 i 查找 k
                int curR(0);
                if (i - 1 < 0) {
                    curR = xorN[k];
                } else {
                    curR = xorN[k] ^ xorN[i - 1];
                }
                if (curR == 0) {
                    result += (k - i);
                }
            }
        }

        return result;
    }
};

算法时间复杂度为 O ( N 2 ) O(N^2) O(N2)

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

本题只要找到合适的方式表示乘客上下车的时机即可。可以利用数组，将乘客上车时记为正数，下车时记为负数，构造上下车数组。之后遍历该数组，对每一时间点计算前缀和，该和即为当前时间车上乘客的数量，确保该数量不超过最大载客数量即可：

class Solution {
public:
    bool carPooling(vector>& trips, int capacity) {
        int pass[1001]{0}; // 使用数组表示区间内乘客人数，正数表示上车，负数表示下车
        for (int i = 0; i < trips.size(); ++i) {
            vector& curTrip = trips.at(i);
            pass[curTrip[1]] += curTrip[0]; // 同一 km 有上有下
            pass[curTrip[2]] += -curTrip[0];
        }

        // 通过 pass 的前缀和计算每个距离时的乘客数量
        int passNum[1001]{0}; // 乘客上下区间
        passNum[0] = pass[0];
        if (passNum[0] > capacity) {
            return false;
        }
        for (int i = 1; i < 1001; ++i) {
            passNum[i] = pass[i] + passNum[i - 1];
            if (passNum[i] > capacity) {
                return false;
            }
        }

        return true;
    }
};

算法时间复杂度为 O ( N ) O(N) O(N)

前缀和是一个很有用的表达方式，通常将实际事务表示为各种数据结构能够有效帮助计算。