[LeetCode] 303. 区域和检索 - 数组不可变 ☆(动态规划)
2023-09-14 09:07:34 时间
描述
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
解析
很明显想到动态规划，一维数组即可。存放当前index到index=0的数组和。
代码
static int[] dp; public static void NumArray1(int[] nums) { dp = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { dp[i + 1] = dp[i] + nums[i]; } System.out.println(JSON.toJSONString(dp)); } public static int sumRange1(int i, int j) { return dp[j + 1] - dp[i]; }
相关文章
- Java实现 LeetCode 714 买卖股票的最佳时机含手续费（动态规划 || 迭代法）
- Java实现 LeetCode 677 键值映射（字典树）
- Java实现 LeetCode 629 K个逆序对数组（动态规划+数学）
- Java实现 LeetCode 600 不含连续1的非负整数（有些题为了避免使用位运算可以换成动态规划）
- Java实现 LeetCode 525 连续数组
- Java实现 LeetCode 495 提莫攻击
- Java实现 LeetCode 343 整数拆分（动态规划入门经典）
- Java实现 LeetCode 111 二叉树的最小深度
- LeetCode-764. 最大加号标志【动态规划，二维数组】
- Leetcode学习计划之动态规划入门day19(392,1143,72)
- Leetcode学习计划之动态规划入门day17(5,516)
- Leetcode学习计划之动态规划入门day9(139,42)
- Leetcode学习计划之动态规划入门day8(309,714)
- Leetcode学习计划之动态规划入门day7(1014,121,122)
- LeetCode - 1723 完成所有工作的最短时间
- 【LeetCode Python实现】300. 最长递增子序列（中等）动态规划
- Leetcode 80. 删除有序数组中的重复项 II
- Leetcode 2176. 统计数组中相等且可以被整除的数对
- Leetcode 1013. 将数组分成和相等的三个部分（终于解决）
- [LeetCode] 16. 最接近的三数之和 ☆☆☆(双指针)
- [LeetCode] 392. 判断子序列 ☆(动态规划)