FilesExpand file tree

master

/

_307_NumArray.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

58 lines (52 loc) · 1.53 KB

master

/

_307_NumArray.java

Copy path

Top

File metadata and controls

• Code
• Blame

58 lines (52 loc) · 1.53 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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;

}

}

}