区间和

题目：

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

解法-通过前缀和数组

思路：由于暴力求解时间复杂度较大，因此采用前缀和的方法

  1. 引入前缀和数组：presum[i]表示前i个元素的和
  2. 如果要计算的区间为[begin,end]，则计算presum[end]-presum[begin-1]
  3. 这里的begin 和 end 都是从0开始

复杂度：

  • 时间复杂度：
  • 空间复杂度：

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int solution(vector<int>&nums,int begin,int end)
{
    int sum = 0;
    int result = 0;
    vector<int> presum(nums.size(),0);
    for (int i = 0; i < nums.size(); i++)
    {
        sum += nums[i];
        presum[i]=sum;
        cout<<"presum["<<i<<"] = "<<presum[i]<<endl;
    }
    result = presum[end]-presum[begin-1];
    return result;
}

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。