[303] Range Sum Query - Immutable

太奸詐了！！！原來不是要存原本的array 是嗎！！！

typedef struct {

int size;

int* arr;

} NumArray;

NumArray* numArrayCreate(int* nums, int numsSize) {

int* ret = malloc (sizeof(int)*numsSize);

// for (int i=0;i<numsSize;i++)

// ret[i]=nums[i];

memcpy(ret,nums,sizeof(int)*numsSize);

NumArray* ptr = malloc (sizeof (NumArray) * 1);

ptr->arr = ret;

ptr->size = numsSize;

return ptr;

}

int numArraySumRange(NumArray* obj, int left, int right) {

int sum = 0;

for (int i =left;i<=right;i++)

sum+= obj->arr[i];

return sum;

}

void numArrayFree(NumArray* obj) {

free(obj->arr);

free(obj);

}

/**

* Your NumArray struct will be instantiated and called as such:

* NumArray* obj = numArrayCreate(nums, numsSize);

* int param_1 = numArraySumRange(obj, left, right);

* numArrayFree(obj);

*/

好的～經過了修改～採用prefix sum 的精神～

然後因為第一個index 的意外卡了一下(苦笑)

typedef struct {

int size;

int* arr;

} NumArray;

NumArray* numArrayCreate(int* nums, int numsSize) {

int* ret = malloc (sizeof(int)*numsSize);

int sum=0;

for (int i=0;i<numsSize;i++)

{

ret[i]=sum+nums[i];

sum+=nums[i];

}

NumArray* ptr = malloc (sizeof (NumArray) * 1);

ptr->arr = ret;

ptr->size = numsSize;

return ptr;

}

int numArraySumRange(NumArray* obj, int left, int right) {

int ret=obj->arr[right];

if (left==0)

return ret;

return ret - obj->arr[left-1];

}

void numArrayFree(NumArray* obj) {

free(obj->arr);

free(obj);

}

/**

* Your NumArray struct will be instantiated and called as such:

* NumArray* obj = numArrayCreate(nums, numsSize);

* int param_1 = numArraySumRange(obj, left, right);

* numArrayFree(obj);

*/

而且原來直接取前一個值來相加嗎XD 我好笨XD

NumArray* numArrayCreate(int* nums, int numsSize) {

int* ret = malloc (sizeof(int)*numsSize);

ret[0]=nums[0];

for (int i=1;i<numsSize;i++)

ret[i]=ret[i-1]+nums[i];

NumArray* ptr = malloc (sizeof (NumArray) * 1);

ptr->arr = ret;

ptr->size = numsSize;

return ptr;

}