这是悦乐书的第 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 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/29862f24f418