文档章节

leetcode-DP-   303. Range Sum Query - Immutable

梦想游戏人
 梦想游戏人
发布于 2016/09/17 19:10
字数 154
阅读 5
收藏 0

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

 

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function.

DP解法,先计算0-第i项的和,最终结果就是0-j的和减去0-i-1的和


class NumArray {
public:
	vector<int> sums;
	int s;
	NumArray(  vector<int> nums)
	{
		s = nums.size();
		if (s <= 0)return ;
		sums.reserve(100);

		sums.push_back(nums[0]);

		for (int i = 1; i < nums.size(); i++)
		{

	 
			int a = sums[i - 1] + nums[i];

			sums.push_back(a);


		}

	}


	int sumRange(int i, int j) {
		if (s <= 0)return 0;

		if (i == 0)return sums[j];
		return sums[j]-sums[i-1];
	}
 


};
 

 

 

© 著作权归作者所有

梦想游戏人
粉丝 38
博文 445
码字总数 127977
作品 0
成都
私信 提问
Leetcode 303. Range Sum Query - Immutable

版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn.net/Quincuntial/article/details/87634113 文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Descr...

SnailTyan
02/18
0
0
LeetCode:Range Sum Query 2D -Immutable-矩阵指定区域内的元素和

1、题目名称 Range Sum Query 2D(矩阵指定区域内的元素和) 2、题目地址 https://leetcode.com/problemset/algorithms/ 3、题目内容 英文:Given a 2D matrix matrix, find the sum of the...

北风其凉
2015/11/15
0
0
[LeetCode] Range Sum Query 2D - Mutable 二维区域和检索 - 可变

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). The above rectangl......

机器的心脏
2017/12/15
0
0
[LeetCode] Count of Range Sum 区间和计数

Given an integer array , return the number of range sums that lie in inclusive. Range sum is defined as the sum of the elements in between indices and ( ≤ ), inclusive. Note: ......

机器的心脏
2017/12/15
0
0
LeetCode:Range Sum Query - Immutable - 数组指定区间内的元素和

1、题目名称 Range Sum Query(数组指定区间内的元素和) 2、题目地址 https://leetcode.com/problems/range-sum-query-immutable/ 3、题目内容 英文:Given an integer array nums, find t...

北风其凉
2015/11/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

JWT学习总结

官方 https://jwt.io 英文原版 https://www.ietf.org/rfc/rfc7519.txt 或 https://tools.ietf.org/html/rfc7519 中文翻译 https://www.jianshu.com/p/10f5161dd9df 1. 概述 JSON Web Token(......

冷基
今天
3
0
AOP的学习(1)

AOP 理解AOP编程思想(面向方法、面向切面) spring AOP的概念 方面 -- 功能 目标 -- 原有方法 通知 -- 对原有方法增强的方法 连接点 -- 可以用来连接通知的地方(方法) 切入点 -- 将用来插入...

太猪-YJ
今天
4
0
一张图看懂亮度、明度、光度、光亮度、明亮度

亮度、明度、光亮度,Luminance和Brightness、lightness其实都是一个意思,只是起名字太难了。 提出一个颜色模型后,由于明度的取值与别人的不同,为了表示区别所以就另想一个词而已。 因此在...

linsk1998
昨天
8
0
Python应用:python链表示例

前言 python链表应用源码示例,需要用到python os模块方法、函数和类的应用。 首先,先简单的来了解下什么是链表?链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是...

python小白1
昨天
4
0
Source Insight加载源码

Source Insight是一个图形化的源代码查看工具(当然也可以作为编译工具)。如果一个项目的源代码较多,此工具可以很方便地查找到源代码自建的依赖关系。 1.创建工程 下图为Snort源代码的文件...

天王盖地虎626
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部