leetcode - 303.區域和檢索-數組不可變（動态規劃）

303.區域和檢索-數組不可變

——————————————————————————————————————————

給定一個整數數組 nums，求出數組從索引 i 到 j (i ≤ j) 範圍内元素的總和，包含 i, j 兩點。

示例：

給定 nums = [-2, 0, 3, -5, 2, -1]，求和函數為 sumRange()

sumRange(0, 2) -> 1

sumRange(2, 5) -> -1

sumRange(0, 5) -> -3

說明:

你可以假設數組不可變。

會多次調用 sumRange 方法。

——————————————————————————————————————————

題目來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/range-sum-query-immutable

——————————————————————————————————————————

題目了解

這個題目了解很簡單，給定一個數組，設計一個求和函數。但該題目提示會多次調用sumRange方法，如果在求和函數sumRange()參數不變的情況下調用1000次，這樣會浪費很多時間。是以需要使用動态規劃，有效地提高效率。當然，直接使用暴力解法也是可以的。這裡我們使用C++進行求解。

解法一：暴力解法

暴力解法簡單暴力，直接計算sum區間的和，然後return，以下是C++代碼：

class NumArray {
private:
    vector<int> data;  //建立一個數組
    
public:
    NumArray(vector<int>& nums)
     {
        for(int i=0;i<nums.size();i++)
            data.push_back(nums[i]);  //使用push_back将num的元素放進data裡面
    }
    
    int sumRange(int i, int j)  //求和函數
     {
        int sums = 0;
        for(int k=i;k<=j;k++)  //循環參數之間的值，進行求和
        {
            sums = sums + data[k];
        }
        return sums;  //傳回求和
    }
};

           

解法二：緩存資料（一）

暴力解法比較直接，但在相同的i，j參數條件下重複使用1000次求和函數，暴力解法就會顯得太麻煩了。是以，可以将所有可能的組合群組合對應的值組合起來，存放在一個表中，在需要的時候，直接查詢i，j組合，然後輸出i，j組合對應的求和的值，這裡用空間換取時間，在增加記憶體的情況下能夠更有效率地得到結果。使用哈希表，key對應于求和函數的變量（i,j），value對應于求和函數求得的值。具體代碼如下：

class NumArray {
private:
    map<pair<int,int>,int> Map;  //建立哈希表，結構類似((0,2),1)，即數組索引為0到2之間的和為1
public:
    NumArray(vector<int>& nums) {
        int length = nums.size();
        for(int i=0;i<length;i++)   //循環，計算所有可能出現的組合，放在哈希表中
        {
            int sum = 0;
            for(int j=i;j<length;j++)
            {
                sum = sum + nums[j];
                Map[pair<int,int>(i,j)] = sum;
            }
        }
    }
    
    int sumRange(int i, int j)
    {
        return Map[pair<int,int>(i,j)];   //根據i和j的參數傳回對應的value
    }
};
           

但是，很尴尬，運作的時候逾時了，十六個測試用例隻過了十五個。如果同學知道原因的話，希望您可以和我講解一下，本人比較菜，哈哈。

解法三：緩存資料（二）

上面的緩存資料（一）方法有一個很大的問題就是需要很大的記憶體空間，因為需要考慮所有的情況。這裡介紹的第二種情況是更簡潔的緩存資料的辦法。比如我們需要求資料中nums[i]到nums[j]的和，則可以使用sum[j] - sum[i]來得到，這裡sum[i]是前i個資料的和，sum[j]是前j個資料的和，這樣通過相減，就可以得到nums[i]到nums[j]之間的資料之和。同時，我們隻需要提前儲存前n個資料之和，就可以得到任意組合的資料之和了。既節省了空間也節省了時間。具體的C++代碼如下：

class NumArray {
private:
    vector<int> arrays;  //建立一個容器數組
public:
    NumArray(vector<int>& nums) {
        int length = nums.size();  //計算nums數組的長度
        int sums = 0;
        arrays.push_back(0);   //這裡使用一下技巧，讓arrays的第一個數是0
        for(int i=0;i<length;i++)
        {
            sums = sums + nums[i];  //計算前n個數的和
            arrays.push_back(sums);
            cout<<sums;
        }
    }
    
    int sumRange(int i, int j) {
        return arrays[j+1] - arrays[i];  //這裡因為開始的時候push_back了一個元素0，是以是j+1
    }
};
           

上面的三種解法中，最好的肯定是第三種解法了。這些全部列出來，隻是為了能夠讓自己了解更深刻，一步一步進步，如果有什麼錯誤的地方，歡迎指出。