【Leetcode 303】关关的刷题日记67–Leetcode 303 Range Sum Query

会员服务 ·

【Leetcode 303】关关的刷题日记67–Leetcode 303 Range Sum Query – Immutable

关关

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记67 – Leetcode 303 Range Sum Query – Immutable

题目

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example: Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 Note: You may assume that the array does not change. There are many calls to sumRange function.

题目的意思是给定一个数组，求指定子序列的和。数组是不发生变化的，而且会多次求子序列的和。

思路

思路：如果要是每次都遍历数组求子序列和的话，因为会调用很多次肯定会超时。所以我们设置数组re，re[i]表示该数组前i个元素的和。每次调用sumRange的时候，直接返回re[j]-re[i-1]即可。

class NumArray {public:
    vector<int>re;

    NumArray(vector<int> nums) {
        int sum=0;
        for(int i=0; i<nums.size(); i++)
        {
            re.push_back(sum+nums[i]);
            sum=re[i];
        }
    }

    int sumRange(int i, int j) {
        if(i==0)
            return re[j];
        return re[j]-re[i-1];
    }};/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */