Leetcode 区域和检索 - 数组可修改
程序员文章站
2022-03-11 21:42:55
...
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。
示例:
Given nums = [1, 3, 5] sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8
说明:
- 数组仅可以在 update 函数下进行修改。
- 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
思路:顺着Leetcode 区域和检索 - 数组不可变 的思路,保留前n项和,更新时只更新前n项和。
typedef struct {
int *sums;
int size;
} NumArray;
NumArray* numArrayCreate(int* nums, int numsSize) {
NumArray *ret = malloc(sizeof(NumArray));
int i;
ret->size = numsSize;
ret->sums = malloc(sizeof(int) * numsSize);
if(!numsSize)
return ret;
ret->sums[0] = nums[0];
for(i = 1; i < numsSize; i++) {
ret->sums[i] = 0;
ret->sums[i] += ret->sums[i - 1] + nums[i];
}
return ret;
}
void numArrayUpdate(NumArray* obj, int i, int val) {
int k;
if(i == 0)
val = val - obj->sums[i];
else
val = val - (obj->sums[i] - obj->sums[i-1]);
for(k = i; k < obj->size; k++) {
obj->sums[k] += val;
}
}
int numArraySumRange(NumArray* obj, int i, int j) {
if (i == 0)
return obj->sums[j];
else
return obj->sums[j] - obj->sums[i - 1];
}
void numArrayFree(NumArray* obj) {
free(obj);
}