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內所有數的總和。
#A:
這個BF比較直觀子檀，但時間復雜度不是最優(yōu)。因為有個for loop峦树，所以時間復雜度是O(n)鸭叙。
Q：為什么這個會Time Limit Exceeded（超時）酝惧？
如果array里面數字少竟宋，算range sum其實還好逻卖，效率應該是不錯的吧!?但是如果數字大了叨吮，最極限的情況辆布，比如 `int[] test = new int[1000000]；`那要是我們求`.sumRange(3茶鉴，999999)`锋玲，loop trace基本無限趨近于O（n）了。所以涵叮，放大測試惭蹂，就會發(fā)現問題。
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++) { //這里有個for loop, 所以時間復雜度：O（n）
sum += data[k];
}
return sum;
}
這個最優(yōu)割粮，時間復雜度O（1）盾碗，空間復雜度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) //這個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];
}
這個處理起來有點兒繞廷雅，要多declaration一個array。另外畢竟length不一樣京髓，要加1航缀。
優(yōu)點是不需要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，~~還得自己定義對象Pair~~急迂，**map可以當做一個容器（裝載具有一定格式的數據）备图；pair可以理解為元素（放入到容器的的一個個個體）灿巧，發(fā)現pair并沒有單獨行動的典型用法赶袄，正常都是配合map來使用（即把pair這個元素插入到map這個容器里面）。pair 是 一種模版類型抠藕。每個pair 可以存儲兩個值饿肺。這兩種值無限制。也可以將自己寫的struct的對象放進去幢痘，去處理一對兒不同類型的值唬格。** LeetCode討論里家破，貌似有人說程序用不了颜说，可能是沒有自己定義Pair類，Java標準庫里沒有這個類汰聋，這個數據類型得自己定義一下才能用吧门粪。貌似C++可以直接用，除非是兩個值數據類型不同烹困，才得自己寫個struct玄妈。（這塊兒不是100%確定...）：| `Map<Pair<Integer, Integer>, Integer>`，并且需要一個O（n^2）的pre-computation髓梅，因為要put數據到一個二維map里拟蜻。但是每個sumRange query的時間是O（1），HashTable的look up運行時長是個定值枯饿。
----
#Notes：
----
**好像**：當"pre-computation done in the constructor"酝锅，在考慮sumRange方法的query's time，計算這個方法（算法）的時間復雜度時奢方，pre- 部分可以不計入搔扁。
###Dynamic Programming（動態(tài)規(guī)劃）：
- 線性動規(guī)
- 區(qū)域動規(guī)
- 樹形動規(guī)
- 背包問題