数组-前缀和技巧

数据结构与算法 shanhuhai 406℃ 0评论

题目:https://leetcode-cn.com/problems/range-sum-query-immutable/

解题思路一:遍历数组

传统的方法就是遍历数组,时间复杂度为 O(N)


class NumArray {
    private int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
    }
    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}

这个比较简单,我们重点看下前缀和的解法。

解题思路二:使用前缀和技巧

首先根据传入的数组,计算一个新的数组,
新数组的每项为传入数组的前N个元素的和。

例如传入数组为 int[] nums = [1,3,-1,5,2]
那么新数组
第0项为:perSum[0] = 0 (固定让第0个元素为0,方便后面计算累加和)
第1项为:perSum[1] = 1int[1] = 1
第2项为:perSum[2] = 1+3,即int[2]=4
第3项为:perSum[3] = 1+3+(-1),即int[2]=3
….
以此类推
第5项为:perSum[6] = 1+3+(-1)+5+2 int[5]=10

所以从传入的数组 int[] nums = [1,3,-1,5,2]
我们得到一个新数组 int[] perSum =[0,1,4,3,8,10] 这个数组从第0项固定为0, 从第i(i>0)项开始,为nums 数组中从第0项到第i项的和。

得到新数组后,我们就可以通过简单的减法来计算传入的数组, 任意两个索引之间元素的和。
例如我想计算索引区间 [1,4]的元素的和,就可以通过 perSum[5]-perSum[1] 得出

注意:新数组的元素个数要比传入数组的元素多一个,因为新数组设置第0个元素为0 ,这是为了方便计算累加和

class NumArray {
    private int[] perSum;

    public NumArray(int[] nums) {
        this.perSum = new int[nums.length +1];
        for(int i = 1; i< this.perSum.length; i++ ){
            perSum[i] = perSum[i-1] + nums[i-1];
        }
    }
    
    public int sumRange(int left, int right) {
        return perSum[right+1] - perSum[left];
    }
}

这种技巧有点类似于高斯计算等差数列的和,有异曲同工之妙吧。
这种解法的时间复杂度是O(1),因为不论有多少个数组元素,获取某个区间的和只是计算一次减法。

转载请注明:大后端 » 数组-前缀和技巧

付费咨询
喜欢 (32)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址