[LeetCode]303. Range Sum Query - Immutable ★

每天一道编程题题目描述样例python解法C语言解法题目描述Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.题目大意给定一个数字数组计算其中下标从 i 到 j 的元素的和ij 均合法且为闭区间。样例Example:Given nums [-2, 0, 3, -5, 2, -1]sumRange(0, 2) - 1sumRange(2, 5) - -1sumRange(0, 5) - -3python解法classNumArray:def__init__(self,nums:List[int]):self.nums[]fori,ninenumerate(nums):ifi!0:self.nums.append(self.nums[i-1]n)else:self.nums.append(n)defsumRange(self,i:int,j:int)-int:returnself.nums[j]-(iandself.nums[i-1])Runtime: 96 ms, faster than 54.19% of Python3 online submissions for Range Sum Query - Immutable.Memory Usage: 17.3 MB, less than 10.00% of Python3 online submissions for Range Sum Query - Immutable.题后反思这种题目最简单的思路就是直接将nums赋值给一个实例变量然后给出范围是直接相加但是这种方式无形中导致重复计算了很多次.所以为了改进算法可以在初始化的时候将列表的其实位置到当前位置的和计算好在计算某个范围的和时直接做一次减法就可以了。因为求的是闭区间的元素的和所以在相减的时候下标为i的元素需要判断是否越界。C语言解法typedefstruct{int*data;}NumArray;NumArray*numArrayCreate(int*nums,intnumsSize){NumArray*num(NumArray*)malloc(sizeof(NumArray));num-data(int*)malloc(sizeof(int)*(numsSize1));num-data[0]0;for(inti1;inumsSize;i){num-data[i]num-data[i-1]nums[i-1];}returnnum;}intnumArraySumRange(NumArray*obj,inti,intj){returnobj-data[j1]-obj-data[i];}voidnumArrayFree(NumArray*obj){free(obj-data);free(obj);}Runtime: 24 ms, faster than 72.22% of C online submissions for Range Sum Query - Immutable.Memory Usage: 12.5 MB, less than 33.33% of C online submissions for Range Sum Query - Immutable.题后反思C语言解法中多申请了一个空间存放了0从而保证了j1不会越界ij都合法的前提下文中都是我个人的理解如有错误的地方欢迎下方评论告诉我我及时更正大家共同进步