每天进步一点点🤏

区域和检索-数组不可变

  • ~1.93K 字

区域和检索-数组不可变

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给定一个整数数组  nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和,其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和,包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

 

示例 1：
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
思路:
常规思路是直接遍历数组求和,但sumRange方法或多次调用,可能会造成性能瓶颈
解法是每个下标的值存储为之前所有值之和, 那么求区间内的值就是将区间头尾下标的值相减
相当于0~尾部区间的所有值相加,减去0~头区间所有值相加的部分,剩下的部分就是头部~尾部区间所有值之和

代码:
private $nums;

function __construct($nums)
{
    $dp = [0];

    // nums  1, 2    , 3    , 4    , 5     , 6
    // dp    0, 1=0+1, 3=1+2, 6=3+3, 10=6+4, 15=10+5, 21=16+6
    // index 0, 1    , 2    , 4    , 4     , 5      , 6
    for ($i = 0; $i <= count($nums); $i++) {
        // 每个位置的值,是之前所有值的总和
        // $dp[$i + 1]-$dp[$i] = $nums[$i];
        // $dp[$i + 2]-$dp[$i] = $nums[$i+1];
        // $dp[$i + 2]-$dp[$i] = $nums[$i]+$nums[$i+1];
        // $dp[$i + 3]-$dp[$i] = $nums[$i]+$nums[$i+1]+$nums[$i+2];
        // $dp[$i + n + 1]-$dp[$i] = $nums[$i]+$nums[$i+1]+....+$nums[$i+$n];
        $dp[$i + 1] = $dp[$i] + $nums[$i];
    }
    $this->nums = $dp;
}

/**
 * @param Integer $left
 * @param Integer $right
 *
 * @return Integer
 */
function sumRange($left, $right)
{
    // 只需将右边的值减去左边就是区间内的数字之和
    // 比如right = 5,值就是0-4的和区间包含right的位置所以要+1变成0-5的和
    // 比如left = 3，值就是0-2的区间之和, 相减就是3-5区间数字的和
    return $this->nums[$right + 1] - $this->nums[$left];
}