这是悦乐书的第204次更新,第214篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第70题(顺位题号是303)。给定整数数组nums,找到索引i和j(i≤j)之间的元素之和,包括端点。例如:
给定nums = [-2,0,3,-5,2,-1]
sumRange(0,2) - > 1
sumRange(2,5) - > -1
sumRange(0,5) - > -3
注意:
您可以假设数组不会更改。
sumRange函数有很多调用。
本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。
02 第一种解法
使用暴力解法,直接使用for循环依次将i到j之间的元素求和,最后再返回其和。
此解法空间复杂度是O(1),时间复杂度是O(n)。
class NumArray {
public int[] arr;
public NumArray(int[] nums) {
arr = nums;
}
public int sumRange(int i, int j) {
int sum = 0;
for (int k=i; k<= j; k++) {
sum += arr[k];
}
return sum;
}
}
03 第二种解法
如果使用第一种解法,sumRange的方法调用次数太多,并且每次都要重新开始计算,我们可以事先把不同位置元素的和算出来存到另外一个数组中,在sumRange中直接去新数组中取对应位置的和做减法即可。
此解法时间复杂度是O(1),空间复杂度是O(n)。
class NumArray2 {
public int[] sum;
public NumArray2(int[] nums) {
sum = new int[nums.length+1];
for (int i=0; i<nums.length; i++) {
sum[i+1] = nums[i] + sum[i];
}
}
public int sumRange(int i, int j) {
return sum[j+1] - sum[i];
}
}
04 小结
算法专题目前已连续日更超过两个月,算法题文章70+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。
以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!