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
    }
};
           

上面的三种解法中，最好的肯定是第三种解法了。这些全部列出来，只是为了能够让自己理解更深刻，一步一步进步，如果有什么错误的地方，欢迎指出。