【算法集训】基础算法：前缀和 | 习题篇

习题

1480. 一维数组的动态和

简单的前缀和

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

724. 寻找数组的中心下标

#define maxn 10001
int sum[maxn]; //定义前缀和数组


int pivotIndex(int* nums, int numsSize) {
    sum[0] = nums[0];
    for(int i = 1; i < numsSize; ++i) {
        sum[i] = sum[i - 1] + nums[i];
    }
    if(sum[numsSize - 1] - sum[0] == 0) return 0;
    int ans = -1;
    for(int i = 1; i < numsSize; ++i) {
        if(sum[i - 1] == sum[numsSize - 1] - sum[i]) {
            ans = i;
            break;
        }
    }
    return ans;
}

通过定义左右的和，并依次做变换如果相等则得到结果。
要找的是最左边的，所以先把右边加满。
左边+1，右边-1，如果相等则返回。

int pivotIndex(int* nums, int numsSize) {
    int left = 0;
    int right = 0;
    for(int i = 0; i < numsSize; ++i) {
        right += nums[i];
    }
    for(int i = 0; i < numsSize; ++i) {
        right -= nums[i];
        if(right == left) return i;
        left += nums[i];
    }
    return -1;
}

1310. 子数组异或查询

#define MAXX 30001
int xor[MAXX];

int* xorQueries(int* arr, int arrSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int * ret = (int *)malloc(sizeof(int) * queriesSize);
    *returnSize = queriesSize;
    
    xor[0] = arr[0];
    for(int i = 1; i < arrSize; ++i) {
        xor[i] = xor[i - 1] ^ arr[i];
    }
    int ans = 0;
    for(int i = 0; i < queriesSize; ++i) {
        //获取queries的左右值
        int l = queries[i][0];
        int r = queries[i][1];
        if(l == 0) {
            ans = xor[r]; //如果从头开始则直接返回r的值
        }else {
            ans = xor[r] ^ xor[l - 1];  //否则需要减去前面截取的部分
        }
        ret[i] = ans;
    }
    return ret;
}

974. 和可被 K 整除的子数组

#define MAX 30001
int sum[MAX];
int hash[MAX];

int subarraysDivByK(int* nums, int numsSize, int k) {
    int ans = 0;
    sum[0] = nums[0] % k;
    if(sum[0] < 0) sum[0] += k;
    memset(hash, 0 ,sizeof(hash));

    for(int i = 1; i < numsSize; ++i) {
        sum[i] = (sum[i - 1] + nums[i]) % k;
        if(sum[i] < 0) sum[i] += k;
    }
    hash[0] = 1;
    for(int j = 0; j <numsSize; ++j) {
        ans += hash[sum[j]];
        hash[ sum[j] ] ++;
    }
    return ans;
}

2485. 找出中枢整数

这一题是简单题，和前面套路一样，算出前缀和之后进行判断就可以了。

int sum[1001];

int pivotInteger(int n) {
    if(n == 1) return 1;
    sum[1] = 1;
    for(int i = 2; i <= n; ++i) {
        sum[i] = sum[i - 1] + i;
    }
    for(int i = 1; i <= n; ++i) {
        if(sum[i] == sum[n] - sum[i - 1]) {
            return i;
        }
    }
    return -1;
}

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

这道题如何将每个奇数组找出来想了一段时间，思路能想出来就是代码费了点时间。

int sum[110];

int sumOddLengthSubarrays(int* arr, int arrSize){
    // 前缀和
    sum[0] = arr[0];
    int ret = arr[0];
    for(int i = 1; i < arrSize; ++i) {
        sum[i] = sum[i - 1] + arr[i];
        ret += arr[i];
    }
    int step = 2;
    // 外层设置步长
    while(step < arrSize) {
        int sub = step + 1;
        // 内层根据题目要求加
        for(int i = step; i < arrSize; i++) {
            if(i - sub < 0) {
                ret += sum[i];
            }else {
                ret += sum[i] - sum[i - sub];
            }
        }
        step += 2;
    }
    return ret;
}

930. 和相同的二元子数组

int hash[60001];
int sum[30001];

int numSubarraysWithSum(int* nums, int numsSize, int goal){
    memset(hash, 0, sizeof(hash));
    ++hash[ goal ];
    sum[0] = nums[0];
    for(int i = 1; i < numsSize; ++i) {
        sum[i] = sum[i - 1] + nums[i];
    }
    int ans = 0;
    for(int i = 0; i < numsSize; ++i) {
        ans += hash[ sum[i] ];
        ++hash[ sum[i] + goal ];
    }
    return ans;
}