2021-02-20

LeetCode C++ Range Sum Query - Immutable 區域和檢索

今天要練習的 LeetCode 題目是 Range Sum Query - Immutable 區域和檢索，並且以 C++ 實作出來。

Range Sum Query 總共有四種題型：

Range Sum Query — Immutable
Range Sum Query — Mutable
Range Sum Query 2D — Immutable
Range Sum Query 2D — Mutable
這一篇是介紹四個當中的 Range Sum Query — Immutable

LeetCode 題目

https://leetcode.com/problems/range-sum-query-immutable/description/
難度：簡單 Easy
類型：動態規劃 Dynamic Programming

Range Sum Query — Immutable 是 LeetCode 題目的第303題，
題目是要你實做一個 NumArray 類別，給一個 nums [-2, 0, 3, -5, 2, -1] 序列，使用 sumRange(i, j) 時要能夠回傳 [i, j] 範圍內的和，如果題目到這個話就太好了～但是它有個條件就是 sumRange 會頻繁呼叫，呼叫很多次，意味著我心裡的那個解法瞬間瓦解，這時我心中的頓時沉了下來，恩～這我好好來想想怎麼解。

解題思路與答案

以下為我的解題思路，一開始就別管題目的 [-2, 0, 3, -5, 2, -1]，我直接改用 [1,2,3,4] 簡化複雜程度，開始推敲要怎麼解，接著拿出紙筆在上面寫著這幾個數字，我心想著先把 sum 算好之後要 sumRange() 取得時盡量作個簡單運算就回傳了，這樣比在當下用迴圈迭代累加還快，接著在下面寫著每個目前累積的 sum [1,3,6,10]，開始用 sumRange(1,3)、sumRange(1,2)、sumRange(2,3) 這幾組去推演出個規律，如果能在這幾組找到規律那應該適用大部分情況，結果真的找到規律了，如下所示，

[1, 2, 3, 4]
[1, 3, 6, 10]
sumRange(1,3) = 9 = 10-1
sumRange(1,2) = 5 = 6-1
sumRange(2,3) = 7 = 10-3

那麼 sumRange(i,j) 應該就可以寫成回傳 sum[j] - sum[i-1] 了吧！
不過突然想到這邊還沒考慮到 sumRange(0,2)、sumRange(0,3) 這種前面i是0的情形，立馬在紙上驗證試試，

1 2	sumRange(0,2) = 10 sumRange(0,3) = 6

看來i是0的話，就直接回傳sum[j]就可以了～～～耶

那就來開始寫程式組合一下這兩種情形吧！

cpp-range-sum-query-immutable.cpp

// g++ cpp-range-sum-query-immutable.cpp -o a.out -std=c++11
#include <iostream>
#include <vector>
using namespace std;

class NumArray {
public:
    NumArray(vector<int>& nums) {
        sum.resize(nums.size());
        int s = 0;
        for (int i = 0; i < nums.size(); i++) {
            s += nums[i];
            sum[i] = s;
            //cout << sum[i] << " ";
        }
        //cout << "\n";
    }
    
    int sumRange(int i, int j) {
        return i == 0 ? sum[j] : sum[j] - sum[i-1];
    }
private:
    vector<int> sum;
};

int main() {
    //vector<int> nums = {1, 2, 3, 4};
    //NumArray *numArray = new NumArray(nums);
    //cout << numArray->sumRange(1, 3) << "\n";
    //cout << numArray->sumRange(1, 2) << "\n";
    //cout << numArray->sumRange(2, 3) << "\n";
    //cout << numArray->sumRange(0, 2) << "\n";
    //cout << numArray->sumRange(0, 3) << "\n";

    vector<int> nums = {-2, 0, 3, -5, 2, -1};
    NumArray *numArray = new NumArray(nums);
    cout << numArray->sumRange(0, 2) << "\n"; // return 1 ((-2) + 0 + 3)
    cout << numArray->sumRange(2, 5) << "\n"; // return -1 (3 + (-5) + 2 + (-1)) 
    cout << numArray->sumRange(0, 5) << "\n"; // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

    return 0;
}

PS.解題不單單只能準備面試而已，還可以活化腦細胞XD，在實務上若有這種應用情形還可以應用優化，大幅提高系統的效能！

其它參考
Range Sum Query - Immutable - LeetCode
https://leetcode.com/problems/range-sum-query-immutable/description/
303 区域和检索 - 数组不可变 - 力扣（LeetCode）
https://leetcode-cn.com/problems/range-sum-query-immutable/
[LeetCode] Range Sum Query - Immutable 区域和检索 - 不可变 - Grandyang - 博客园
https://www.cnblogs.com/grandyang/p/4952464.html