forked from pphdsny/Leetcode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path_307_NumArray.java
More file actions
58 lines (52 loc) · 1.53 KB
/
Copy path_307_NumArray.java
File metadata and controls
58 lines (52 loc) · 1.53 KB
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package pp.arithmetic.leetcode;
/**
* Created by wangpeng on 2018/9/29.
* 307.区域和检索 - 数组可修改
* <p>
* 给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
* <p>
* update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
* <p>
* 示例:
* <p>
* Given nums = [1, 3, 5]
* <p>
* sumRange(0, 2) -> 9
* update(1, 2)
* sumRange(0, 2) -> 8
* 说明:
* <p>
* 数组仅可以在 update 函数下进行修改。
* 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。
*
* @see <a href="https://leetcode-cn.com/problems/range-sum-query-mutable/description/">range-sum-query-mutable</a>
*/
public class _307_NumArray {
public static void main(String[] args) {
NumArray numArray = new NumArray(new int[]{1, 3, 5});
System.out.println(numArray.sumRange(0,2));
numArray.update(1,2);
System.out.println(numArray.sumRange(0,2));
}
/**
* 最简单的实现
* update复杂度O(1)
* sum复杂度O(n)
*/
private static class NumArray {
int[] nums;
public NumArray(int[] nums) {
this.nums = nums;
}
public void update(int i, int val) {
nums[i] = val;
}
public int sumRange(int i, int j) {
int total = 0;
for (int k = i; k <= j; k++) {
total += nums[k];
}
return total;
}
}
}