Q:
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3
Note:
You may assume that the array does not change. There are many calls to sumRange function.
public NumArray(int[] nums) {
}
public int sumRange(int i, int j) {
}
// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);
}
注：求的是range內(nèi)所有數(shù)的總和。
#A:
這個(gè)BF比較直觀，但時(shí)間復(fù)雜度不是最優(yōu)。因?yàn)橛袀€(gè)for loop，所以時(shí)間復(fù)雜度是O(n)。
Q：為什么這個(gè)會(huì)Time Limit Exceeded（超時(shí)）？
如果array里面數(shù)字少，算range sum其實(shí)還好，效率應(yīng)該是不錯(cuò)的吧!?但是如果數(shù)字大了，最極限的情況，比如 `int[] test = new int[1000000]；`那要是我們求`.sumRange(3，999999)`，loop trace基本無(wú)限趨近于O（n）了。所以，放大測(cè)試，就會(huì)發(fā)現(xiàn)問(wèn)題。
private int[] data;
public NumArray(int[] nums) {
data = nums; //data is reference
}
public int sumRange(int i, int j) {
int sum = 0;
for (int k = i; k <= j; k++) { //這里有個(gè)for loop, 所以時(shí)間復(fù)雜度：O（n）
sum += data[k];
}
return sum;
}
這個(gè)最優(yōu)，時(shí)間復(fù)雜度O（1），空間復(fù)雜度O（n）
public class NumArray {
int[] nums;
public NumArray(int[] nums) { //pre-caculation
this.nums = nums;
for(int i = 1; i < nums.length; i++)
nums[i] += nums[i - 1];
}
public int sumRange(int i, int j) {
if(i == 0) //這個(gè)if判斷不能省略
return nums[j];
else
return nums[j] - nums[i - 1];
}
}
思路同上，但加入dummy 0，省去if判斷
private int[] sum;
public NumArray(int[] nums) {
sum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
sum[i + 1] = sum[i] + nums[i];
}
}
public int sumRange(int i, int j) {
return sum[j + 1] - sum[i];
}
這個(gè)處理起來(lái)有點(diǎn)兒繞，要多declaration一個(gè)array。另外畢竟length不一樣，要加1。
優(yōu)點(diǎn)是不需要if判斷了。原作者是這么解釋的：
>Notice in the code above we inserted a dummy 0 as the first element in the *sum* array. This trick saves us from an extra conditional check in *sumRange*function.
**Complexity analysis** ：Time complexity : O(1)，Space complexity : O(n)
O(n) time pre-computation. Since the cumulative sum is cached, each *sumRange* query can be calculated in O(1).
----
LeetCode editorial solution approach #2
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();
public NumArray(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
sum += nums[j];
map.put(Pair.create(i, j), sum);
}
}
}
public int sumRange(int i, int j) {
return map.get(Pair.create(i, j));
}
用到了HashMap，~~還得自己定義對(duì)象Pair~~，**map可以當(dāng)做一個(gè)容器（裝載具有一定格式的數(shù)據(jù)）；pair可以理解為元素（放入到容器的的一個(gè)個(gè)個(gè)體），發(fā)現(xiàn)pair并沒(méi)有單獨(dú)行動(dòng)的典型用法，正常都是配合map來(lái)使用（即把pair這個(gè)元素插入到map這個(gè)容器里面）。pair 是 一種模版類型。每個(gè)pair 可以存儲(chǔ)兩個(gè)值。這兩種值無(wú)限制。也可以將自己寫的struct的對(duì)象放進(jìn)去，去處理一對(duì)兒不同類型的值。** LeetCode討論里，貌似有人說(shuō)程序用不了，可能是沒(méi)有自己定義Pair類，Java標(biāo)準(zhǔn)庫(kù)里沒(méi)有這個(gè)類，這個(gè)數(shù)據(jù)類型得自己定義一下才能用吧。貌似C++可以直接用，除非是兩個(gè)值數(shù)據(jù)類型不同，才得自己寫個(gè)struct。（這塊兒不是100%確定...）：| `Map<Pair<Integer, Integer>, Integer>`，并且需要一個(gè)O（n^2）的pre-computation，因?yàn)橐猵ut數(shù)據(jù)到一個(gè)二維map里。但是每個(gè)sumRange query的時(shí)間是O（1），HashTable的look up運(yùn)行時(shí)長(zhǎng)是個(gè)定值。
----
#Notes：
----
**好像**：當(dāng)"pre-computation done in the constructor"，在考慮sumRange方法的query's time，計(jì)算這個(gè)方法（算法）的時(shí)間復(fù)雜度時(shí)，pre- 部分可以不計(jì)入。
###Dynamic Programming（動(dòng)態(tài)規(guī)劃）：
- 線性動(dòng)規(guī)
- 區(qū)域動(dòng)規(guī)
- 樹形動(dòng)規(guī)
- 背包問(wèn)題