[LeetCode] Range Sum Query - Immutable
LeetCode Query sum range Immutable
2023-09-14 09:01:04 时间
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
You may assume that the array does not change. There are many calls to sumRange function.
Lazy Join Optimizations Without Upfront Statistics 立即下载
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
You may assume that the array does not change. There are many calls to sumRange function.
考虑到要多次调用sumRange()函数,因此需要把结果先存起来,调用时就可以直接返回了。最开始考虑的是用dp[i][j]来直接存储i到j之间元素的和,但是内存超出限制。于是考虑用dp[i]来存储0到i之间元素的和,0到j的和减去0到i-1的和即为所求。
// Runtime: 3 ms public class NumArray { private int[] dp; public NumArray(int[] nums) { dp = new int[nums.length]; int sum = 0; for (int i = 0; i nums.length; i++) { sum += nums[i]; dp[i] = sum; public int sumRange(int i, int j) { return i == 0 ? dp[j] : dp[j] - dp[i - 1]; // Your NumArray object will be instantiated and called as such: // NumArray numArray = new NumArray(nums); // numArray.sumRange(0, 1); // numArray.sumRange(1, 2);
Lazy Join Optimizations Without Upfront Statistics 立即下载
相关文章
- leetcode 之Rotate List(18)
- Java实现 LeetCode 554 砖墙(缝隙可以放在数组?)
- Java实现 LeetCode 525 连续数组
- Java实现 LeetCode 206 反转链表
- [LeetCode] Move Zeroes
- 67. 二进制求和——【Leetcode每日一题】
- leetcode 106. 从中序与后序遍历序列构造二叉树
- Leetcode 202. 快乐数(一点都不快乐)
- leetcode Remove Duplicates from Sorted List
- leetcode 108. Convert Sorted Array to Binary Search Tree
- 【Leetcode刷题Python】260. 只出现一次的数字 III
- LeetCode 88. 合并两个有序数组
- LeetCode 142. 环形链表 II
- 【LeetCode】581. 最短无序连续子数组
- 【14】最长公共前缀【LeetCode】