五月集训-08【前缀和】

• 前言
• 一、练习题目
• 二、思路及题解
• • 1. LC1480-一维数组的动态和
  • 2. LC1588-所有奇数长度子数组的和
  • 3. LC1442-形成两个异或相等数组的三元组数目
  • 4. LC1094-拼车
• 总结

        欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 前缀和 专题，更多其他专题内容详见《LeetCode每月集训系列》

方法一：原地修改前缀和

（1）直接上代码。

代码如下：

class Solution {
public:
    vector runningSum(vector& nums) {
        for (int i = 1; i < nums.size(); ++i) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
};

方法一：前缀和

（1）遍历数组求得该数组的前缀和数组；
（2）遍历前缀和数组，得到奇数长度子数组的和。

代码如下：

class Solution {
    public:
    int sumOddLengthSubarrays(vector& arr) {
        int n = arr.size();
        vector prefixSums(n + 1);
        int sum = 0;
        // 1.求得前缀和
        for (int i = 0; i < n; i++) {
            prefixSums[i + 1] = prefixSums[i] + arr[i];
        }
        // 2.求所有奇数长度子数组的和
        for (int length = 1; length <= n; length += 2) {
            for (int start = 0; start + length - 1 < n; start++) {
                sum += prefixSums[start + length] - prefixSums[start];
            }
        }
        return sum;
    }
};

方法一：双重循环

（1）利用异或运算的性质a ⊕ a = 0，所以arr[i] ^...^ arr[j-1]^ arr[j] ^...^ arr[k] = 0；
（2）先遍历得到前缀和数组s，因此s[i] == s[k + 1]；
（3）由0 <= i < j <= k < arr.length可以知道在[i+1, k]范围内的任意j都是符合要求的，则对应的三元组个数即为 j 的数目.

代码如下：

class Solution {
public:
    int countTriplets(vector &arr) {
        int n = arr.size();
        vector s(n + 1);
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] ^ arr[i];
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int k = i + 1; k < n; ++k) {
                if (s[i] == s[k + 1]) {
                    ans += k - i;
                }
            }
        }
        return ans;
    }
};

方法一：差分数组+前缀和

（1）创建一个数组记录每个站点位置上下车后的人数差；
（2）然后通过前缀和计算统计每个站点位置车上的总人数；
（3）将目前车上的总人数和车容量相比是否超过容量。

代码如下：

class Solution {
public:
    bool carPooling(vector>& trips, int capacity) {
        int num[1001], cur = 0;
        memset(num, 0, sizeof(num));
        for (int i = 0; i < trips.size(); ++i) {
            num[trips[i][1]] += trips[i][0];
            num[trips[i][2]] -= trips[i][0];
        }
        for (int i = 0; i < 1001; ++i) {
            cur += num[i];
            if (cur > capacity) return false;
        }
        return true;
    }
};

        题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️