网站建设的风格设置,个人网站推荐免费,免费简历在线制作网站,做网站公司哪个好题目描述#xff1a;
给定一个整数数组 nums#xff0c;处理以下类型的多个查询:计算索引 left 和 right #xff08;包含 left 和 right#xff09;之间的 nums 元素的 和 #xff0c;其中 left right
实现 NumArray 类#xff1a;NumArray(int[] nums) 使用数组…题目描述
给定一个整数数组 nums处理以下类型的多个查询:计算索引 left 和 right 包含 left 和 right之间的 nums 元素的 和 其中 left right
实现 NumArray 类NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 包含 left 和 right 两点也就是 nums[left] nums[left 1] ... nums[right] )示例 1输入
[NumArray, sumRange, sumRange, sumRange]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出
[null, 1, -1, -3]解释
NumArray numArray new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) 0 3)
numArray.sumRange(2, 5); // return -1 (3 (-5) 2 (-1))
numArray.sumRange(0, 5); // return -3 ((-2) 0 3 (-5) 2 (-1))提示1 nums.length 104
-105 nums[i] 105
0 i j nums.length
最多调用 104 次 sumRange 方法
算法
思路
为了减少花费的时间可以直接使用sums得出区域和故可以用 得到索引 到 的区域和
代码实现
# includestdlib.h
typedef struct {int* sums;
} NumArray;NumArray* numArrayCreate(int* nums, int numsSize) {NumArray* ret (NumArray*)malloc(sizeof(NumArray));//创建结构体ret-sums (int*)malloc(sizeof(int) * (numsSize 1));//创建结构体成员数组//sums[i]指的是索引0到i的和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);//释放空间
}
