前缀和，部分题解

文章目录

• 一、前缀和是什么
• 二、前缀和题目

---

一、前缀和是什么

前缀和就是某数列的前n项的和，说白了就是数组的前n项的和，下标从0开始一直加到下标为n的数组的值，综上我们可以直接说数组在n的前缀和。
知道了前缀和，我们就可以知道部分和了，比如说下标i到下标i+l的和
我们就可以用，i+r的前缀和减去i-1的前缀和得到i到i+l的部分和
就是下图这样

我们来看看这一道题
给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。
子数组 定义为原数组中的一个连续子序列。
请你返回 arr 中 所有奇数长度子数组的和 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-of-all-odd-length-subarrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这个题目要用三个循环
第一层循环，确认子数组的开始下标
第二层循环，确认子数组的长度以及每个子数组的末尾元素的下标
第三层，从每个子数组的开始下标遍历到末尾元素的下标

int sumOddLengthSubarrays(int* arr, int arrSize){
    int sum = 0;//定义初始化和的变量
    for (int start = 0;start < arrSize; start++) {//先确定子数组的开始下标
        for (int length = 1;start + length - 1< arrSize;length += 2) {//再求每个子数组的长度
            int end = start + length - 1;//要求是奇数长，所以必须从1开始加2得到长度然后得到每次的子数组的末尾元素的下标
            for (int k = start;k <= end;k++) {//从开始的下标，到末尾下标进行遍历求和
                sum += arr[k];//最后得到的值就是每个奇数长数组的值
            }
        }
    }
    return sum;
}

有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。

给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-highest-altitude
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题的原理就是返回前缀和的最大值

int largestAltitude(int* gain, int gainSize){
    int sum = 0;
    int max = -100;
    for (int i = 0; i < gainSize; i++) {
        sum += gain[i];
        if (max < sum) {
            max = sum;
        }
    }
    if (max <= 0) {
        return 0;
    }
    return max;
}

二、前缀和题目

1480. 一维数组的动态和
      给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
      请返回 nums 的动态和。
      这个题就是求前缀和，没啥难度，一个循环搞定

int* runningSum(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    for (int i = 1;i < numsSize; i++) {
        nums[i] += nums[i - 1];
    }
    return nums;
}

1442. 形成两个异或相等数组的三元组数目

给你一个整数数组 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) 的数目。
这个题目的思路是
先计算每一个下标对应的前缀异或值
枚举一个i，再枚举j，将异或值[j,i-1]塞入hash表
枚举一个k，去哈希表中查找[i,k]的异或和，进行相加
pre^arr[i - 1]表示a
arr[i-1]^arr[k]表示b
用hash去存，然后计算个数

class Solution {
    unordered_map<int, int>hash;
public:
    int countTriplets(vector<int>& arr) {
        int i,j,k,pre;
        int res = 0;
        for (i = 1;i < arr.size();i++) {
            arr[i] ^= arr[i-1];
        }
        for (i = 1;i < arr.size();i++) {
            hash.clear();
            for (j = 0;j < i;j++) {
                if (j==0) {
                    pre = 0;
                } else {
                    pre = arr[j - 1];
                }
                hash[pre^arr[i - 1]]++;//记录异或值，对应加一
            }
            for (k = i; k < arr.size(); k++) {
                res += hash[arr[i-1]^arr[k]];//计算异或值对应相等的个数，也就是之前key的值再次出现的时候
            }
        }
        return res;
    }
};

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/car-pooling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
用一个数组numPassenger来描述乘客上下车的情况，数组的下标是路程的坐标值，在三元组的第二个元素表示该路程下标上客，三元组的第三个元素表示该路程下标下客，每个路程下标标记这个时候乘客的上下车的情况，然后再去遍历0到1000每个路程下标，用sum去累加numPassenger的值，这就是这个路程下标的乘客数量，如果出现sum大于capacity的情况，则表示这个时候车子超载返回false

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        int numPassenger[1002] = {0};
        for (int i = 0;i<trips.size();i++) {
            int cnt = trips[i][0];
            int l = trips[i][1];//上客
            int r = trips[i][2];//下客
            numPassenger[l] += cnt;//上客相加
            numPassenger[r] -= cnt;//下客减少
        }
        int sum = 0;
        for (int i = 0;i<=1000;i++) {//路程最大为1000，遍历每个坐标的上下客人情况
            sum += numPassenger[i];//每个路程下标的乘客数量
            if (sum > capacity) {
                return false;
            }
        }
        return true;
    }
};