本文共 1345 字，大约阅读时间需要 4 分钟。

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点

实现 NumArray 类

NumArray类用于处理整数数组，提供从任意索引 i 到 j（i ≤ j）计算区间和的功能。

类构造方法

类的构造方法接受一个整数数组作为参数，初始化对象的内部数据结构。

区间和的计算方法

通过实现sumRange方法，可以调用该方法即可从索引 i 到 j 求出区间和。

实现思路

在实现NumArray类时，有两种常见的思路：

代码实现

下面是基于上述两种思路的具体代码实现：

#include 
   
    using namespace std;class NumArray {public:    vector
    
      Nums;    NumArray(vector
     
       &nums) {        Nums = nums;    }    int sumRange(int i, int j) {        int sum = 0;        for (int k = i; k <= j; ++k) {            sum += Nums[k];        }        return sum;    }};
     
    
   

#include 
   
    using namespace std;class NumArray {public:    vector
    
      Nums;    vector
     
       PrefixSum; // 前缀和数组    NumArray(vector
      
        &nums) {        int n = nums.size();        Nums = nums;        PrefixSum.resize(n + 1); // 最后一个元素为0，方便后续计算        for (int i = 0; i < n; ++i) {            PrefixSum[i + 1] = PrefixSum[i] + Nums[i];        }    }    int sumRange(int i, int j) {        if (i > j) {            return 0;        }        return PrefixSum[j + 1] - PrefixSum[i];    }};
      
     
    
   

收获

通过预先计算数组的总和，降低了区间和计算的时间复杂度，使得频繁查询区间和的操作更加高效。这也是数据结构和算法优化中的常见技巧之一。