leetcode303. 区域和检索 - 数组不可变

问题连接:303. 区域和检索 - 数组不可变

Problem:

给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。

示例:

1
2
3
4
5
给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()

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

说明:

你可以假设数组不可变。
会多次调用 sumRange 方法。

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package me.liluyang.leetcode;

class NumArray {

private int sums[];
/**
* 303. 区域和检索 - 数组不可变
*
* url: https://leetcode-cn.com/problems/range-sum-query-immutable/comments/
*
* 解题思路:最简单的动态规划
*
* 题目要求的数据是第 i 天到第 j 天的数据和,如果每次求解时都进行循环,效率就比较低调用 n 次 时间复杂度就是 O(n*n)
*
* 这时我们通过生成一个 sums 数组数据和,sum是从第零个节点到第 i 个节点的数据和
*
* 这样我们计算第 i 个元素到第 j 个元素的数据和,就不用了再从 nums 数组求值,变成了从 sums 数据求值:
*
* return i == 0 ? sums[j] : sums[j] - sums[i - 1];
*
* 时间复杂度约为 O(nums.length) + O(n),时间复杂度会降低很多
*
* @param nums
* @return
*/
public NumArray(int[] nums) {
if (nums.length == 0) return;
sums = new int[nums.length];
sums[0] = nums[0];

for (int i = 1; i < nums.length; i++) {
sums[i] = sums[i - 1] + nums[i];
}
}

public int sumRange(int i, int j) {

return i == 0 ? sums[j] : sums[j] - sums[i - 1];
}
}

运行结果截图:

~~~


面条先生 wechat
欢迎关注我的 “知乎日报” 小程序