日拱一卒，月进一步（10）-阿里云开发者社区

日拱一卒，月进一步（10）

2024-05-06 94

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 303. 区域和检索 - 数组不可变 - 力扣（LeetCode）动态规划~

303. 区域和检索 - 数组不可变 - 力扣（LeetCode）

动态规划~

前缀和、

最朴素的思想是存储数组nums的值，每次调用sumRange时，通过循环的方法计算数组nums从下标i到下标j的元素和，需要计算j-i+1个元素的和。由于每次检索的时间和检索的下标范围有关，因此检索的时间复杂度较高，如果检索的次数过多，会超出时间限制。

我们应该尽量降低sumRange的时间复杂度，最理想的时间复杂度是O(1)。

218167e9642594e7f2e4b5aed2b2a74f_f2de7617dd524282ad258d64ac788b1b.png

因此，要计算sumRange(i,j)，则需要计算数组nums在下标i-1和j的前缀和，并计算两个前缀和的差。如果可以在初始化时就计算nums在每个下标的前缀和。即可满足调用sumRange的时间复杂度都是O(1)。

具体实现方面，假设数组的长度nums等于n，创建长度为n+1的前缀和数组nums，sums[i+1]=sums[i]+nums[i]，则sums[i]表示数组从0到下标i-1的前缀和。

将前缀和数组 sum 的长度设为 n+1的目的是为了方便计算 sumRange(i,j)，不需要对 i=0的情况特殊处理。此时有：

8c4eab9c58563be4182edf8f6216a13c_f093d787649c44d7bbfb3a10064d3365.png

typedef struct {
    int* sums;
} NumArray;
 
 
NumArray* numArrayCreate(int* nums, int numsSize) {
    NumArray* ret=malloc(sizeof(NumArray));
    ret->sums=malloc(sizeof(int)*(numsSize+1));
    ret->sums[0]=0;
    for(int i=0;i<numsSize;i++)
    {
        ret->sums[i+1]=ret->sums[i]+nums[i];
    }
    return ret;
    }
 
int numArraySumRange(NumArray* obj, int i, int j) {
    return obj->sums[j+1]-obj->sums[i];
}
 
void numArrayFree(NumArray* obj) {
    free(obj->sums);
}
 
/**
 * Your NumArray struct will be instantiated and called as such:
 * NumArray* obj = numArrayCreate(nums, numsSize);
 * int param_1 = numArraySumRange(obj, left, right);
 
 * numArrayFree(obj);
*/