[leetcode题解]303. Range Sum Query – Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.
  1. There are many calls to sumRange function.

本题是区间和查询,但是由于数组不会变,所以一次初始化之后每次查询只需要做个减法就可以了,如果再添加一个条件,要求有个可更新数组元素的操作,比如区间加x或者区间减x,这个时候就需要用到线段树算法。

这里就是把所有的数组元素进行简单累加,查询的时候根据下标进行减法能得到这段连续区间内的元素和。算法相对比较简单,如下:

typedef struct {
    int *nums;
    int numsSize;
} NumArray;

NumArray* numArrayCreate(int* nums, int numsSize) {
    int i = 0;
    
    NumArray *array = calloc(1, sizeof(NumArray));
    array->nums = calloc(numsSize, sizeof(int));
    array->numsSize = numsSize;
    
    memcpy(array->nums, nums, numsSize * sizeof(int));
    for (i = 1; i < numsSize; i++) {
        array->nums[i] += array->nums[i - 1];
    }
    
    return array;
}

int numArraySumRange(NumArray* obj, int i, int j) {
    if (i < 0)
        i = 0;
    if (j > obj->numsSize - 1)
        j = obj->numsSize - 1;
    
    if (i == 0)
        return obj->nums[j];
    else
        return (obj->nums[j] - obj->nums[i - 1]);
}

void numArrayFree(NumArray* obj) {
    free(obj->nums);
    free(obj);
}

/**
 * Your NumArray struct will be instantiated and called as such:
 * struct NumArray* obj = numArrayCreate(nums, numsSize);
 * int param_1 = numArraySumRange(obj, i, j);
 * numArrayFree(obj);
 */

更多leetcode题解,尽在凌风技术站,www.iaccepted.net


本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]303. Range Sum Query – Immutable

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/154.html

相关文章