当前位置：首页 > news >正文

[LeetCode]303. Range Sum Query - Immutable ★

news 2026/7/28 18:21:37

每天一道编程题

题目描述
样例
python解法
C语言解法

题目描述

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
题目大意：给定一个数字数组，计算其中下标从 i 到 j 的元素的和，i，j 均合法且为闭区间。

样例

Example:

Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

python解法

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)*(numsSize+1));num->data[0]=0;for(inti=1;i<=numsSize;i++){num->data[i]=num->data[i-1]+nums[i-1];}returnnum;}intnumArraySumRange(NumArray*obj,inti,intj){returnobj->data[j+1]-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.
题后反思：