leetcode——区域和检索-白红宇

leetcode——区域和检索

阅读量：592 次

发布时间：2019-03-12

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

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

实现 NumArray 类

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

类构造方法

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

区间和的计算方法

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

实现思路

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

直接实现初始化，每次调用sumRange时遍历数组

这种方法简单实现，但每次计算区间和时都要从头开始遍历数组，时间复杂度为 O(n)，在大数据量时会带来性能问题。

实现初始化的同时计算数组和，每次调用sumRange时直接计算区间和的差

这种方法通过预先计算数组的总和，将sumRange的时间复杂度降低到 O(1)，这种方法在大数组处理时更加高效。

代码实现

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

#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];    }};

收获

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

转载地址：http://zsfxz.baihongyu.com/

你可能感兴趣的文章