五月集训（第八天）前缀和

能看懂英雄哥的题解，我都谢天谢地了！！ 

题1.1480. 一维数组的动态和

代码1

int* runningSum(int* nums, int numsSize, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * numsSize);
    int i, sum;
    sum = 0;
    for(i = 0; i < numsSize; i++){
        sum += nums[i];
        ret[i] = sum;
    }
    *returnSize = numsSize;
    return ret;
}

代码2

int* runningSum(int* nums, int numsSize, int* returnSize){
    int* ret = (int*)malloc(sizeof(int) * numsSize);
    memset(ret, 0, numsSize*4);
    *returnSize = numsSize;
    int sum = 0;
    ret[0] = nums[0];
    for(int i = 1; i < numsSize; i++){
        nums[i] += nums[i - 1];
        sum = nums[i];
        ret[i] = sum;
    }
    return ret;
}

在不调用前缀和的题目里，我对第二个方法感到迷茫....

 题2.1588. 所有奇数长度子数组的和

照搬英雄哥的题解，看完录播理解到之后，感觉太妙了！！！

int sumOddLengthSubarrays(int* arr, int arrSize){
    int i, j, p, ans = 0;
    for(i = 1; i < arrSize; i++){
        arr[i] += arr[i - 1];
    }
    for(i = 1; i <= arrSize; i += 2){
        for(j = i - 1; j < arrSize; j++){
            if(j - i == -1){
                p = 0;
            }else{
                p = arr[j - i];
            }
            ans += arr[j] - p;
        }
    }
    return ans;
}

/1/ 用一个for循环，把数组原地构造成前缀和数组(原数组->前缀和数组)。

/2/ 第一层for构造奇数递增的长度 i，以对应题目条件(构造出奇数个元素的子数组)。长度从1(奇数)开始，每轮加2。

/3/ j = i - 1 是由奇数长度构造出(虚拟)子数组后，用末位元素 j 用来带动长度在原数组里从头走到尾。

/4/ 第二层for循环里的if-else，是用来减去移动后，前面"脱离"长度的元素。从而得到该子数组的和(和的运算及表现形式用前缀和数组)。若为j - i == -1,则当前为第一个子数组(前面没有脱离的元素)，所以 p = 0。之后用ans累加上子数组里元素之和。

/5/两层for循环的条件分别确定了——长度及末位元素 j 不超出数组下标。

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

题4.1094. 拼车