C语言重构【303】区域和检索 - 数组不可变

系统管理员 2022-10-26 04:57 155阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给定一个整数数组  nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
    
    实现 NumArray 类：
    
    NumArray(int[] nums) 使用数组 nums 初始化对象
    int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
     
    
    示例：
    
    输入：
    ["NumArray", "sumRange", "sumRange", "sumRange"]
    [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
    输出：
    [null, 1, -1, -3]
    
    解释：
    NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
    numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
    numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
    numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
     
    
    提示：
    
    0 <= nums.length <= 104
    -105 <= nums[i] <= 105
    0 <= i <= j < nums.length
    最多调用 104 次 sumRange 方法

#### 方案： ####

class NumArray
    { 
    public:
        vector<int> f;
    
    public:
        NumArray(vector<int> &nums)
        { 
            //用一个数组记录前N个总和即可
            int len = nums.size();
            if (len > 0)
            { 
                f.push_back(nums[0]);
                for (int i = 1; i < len; i++)
                { 
                    f.push_back(nums[i] + f[i - 1]);
                }
            }
        }
    
        int sumRange(int i, int j)
        { 
            if (f.size() == 0)
                return 0;
            return i == 0 ? f[j] : f[j] - f[i - 1];
        }
    };
    
    /** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * int param_1 = obj->sumRange(i,j); */

##### 复杂度计算 #####

*  时间复杂度：O(n)，这个是构造时候的复杂度
 *  空间复杂度：O(n)

[Git]: https://github.com/ch98road/leetcode