Day4 EP-303 Range Sum Query - Im

一.问题描述

问题描述

二.问题解决

2.1 暴力大法好。

class NumArray {
public:
   
   NumArray(vector<int> nums) {
    inums=std::move(nums);
   }
   
   int sumRange(int i, int j) {
       int ans = 0 ;
       for (int m=i;m<=j;m++){
           ans+=inums[m];
       }
       return ans;
   }
private:
   vector<int> inums;
};

/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/

没有什么好解释的，暴力大法。但是这里需要自己学习一下自己建造类的功夫。这个部分是自己添加的。

private:
    vector<int> inums;

2.2 简化的预处理。

class NumArray {
public:
    
    NumArray(vector<int> nums) {
     int n = nums.size();
     sums = vector<vector<int>>(n,vector<int>(n,0));
        for(int i =0;i<n;i++){
            for(int j=i;j<n;j++){
                      sums[i][j] = sums[i][j-1]+nums[j];
            }      
        }
    }
    
    int sumRange(int i, int j) {
        return sums[i][j];
    }
private:
    vector<vector<int>> sums;
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

我们可以将我们所有的结果保存在一个二维数组里面，然后当我们需要的时候就直接取出来就好，最简单的方法就是完全的暴力进行计算，每个位置的元素都需要重新计算，这样它的时间复杂度会变成O（n^4, 前两层循环来确定二维数组的位置，后两层决定元素的值。但是我们可以对这个进行简化，我们发现，我们最终的结果实际上只要二维数组的上三角矩阵就好啦，而且每一行的元素之间是有关系的，比如说ans[0][3]=ans[0][2]+nums[3]，这样就将我们的时间复杂度简化到了O（n^2）,也就是上面的代码，但是最终结果还是超时啦

简化的预处理超时

之前的第一种方法没有超时，而现在超时的原因是我们之前要什么求什么，而现在我们将不需要计算的也求出来啦，所以造成了时间的浪费。仅作为一个扩充的思路就好啦。

2.3 神奇的动态规划。

class NumArray {
public:
    NumArray(vector<int> nums) {
        int n = nums.size();
        if(n==0)return;
        sums=vector<int>(n,0);
        sums[0]=nums[0];
        for(int i=1;i<n;i++){
            sums[i]=sums[i-1]+nums[i];
        }
        
    }
    
    int sumRange(int i, int j) {
        if(i==0){
            return sums[j];
        }else{
            return sums[j]-sums[i-1];
        }
    }
    
private:
    vector<int> sums ;
};

本方法是参考网上的比较厉害的方法，主要思想是这样的

1. 首先求了一个数组，数组表示的是从0号到第i号位置的元素的和，同样还是结合我们之前的sums[i]=sums[i-1]+nums[i],从而O(n)就解决了这个问题。
2. 高潮部分来啦。
   我们从第i个元素加到第j个元素，而我们的结果实际上就是sums[j]-sums[i-1];
   举个例子来说。
   sums[1]=a[0]+a[1]
   sums[2]=a[0]+a[1]+a[2]
   sums[5]=a[0]+a[1]+a[2]+a[3]+a[4]+a[5]
   那么我们要求的
   sumRange(2,5)=a[2]+a[3]+a[4]+a[5]=sums[5]-sums[1]=sums[5]-sums[2-1]
   但是需要注意，如果从0开始计算的话，我们就直接返回对应的sums[j]就可以啦。

很厉害的样子，继续加油啦。