303、区域和检索-数组不可变

leetcode 数组前缀和面向对象设计

Created At : 2024-06-02 16:56

Count:428 Views 👀 :

Comment:

题目
1. 示例：
题解
1. 构造前缀和数组

题目

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

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:

你可以假设数组不可变。
会多次调用 sumRange 方法。
$1 <= nums.length <= 10^4$
$-10^5 <= nums[i] <= 10^5$
$0 <= i <= j < nums.length$
最多调用 $10^4$ 次 sumRange 方法

题解

构造前缀和数组

先求出所有的结果
$$ O(n^2) $$
查找需要的结果
$$ O(1) $$

class NumArray {
    private int[][] dp;
    public NumArray(int[] nums) {
        dp = new int[nums.length][];
        int len = nums.length;
        for(int i = 0;i < len;i++) {
            dp[i] = new int[len - i];// 初始化数组
            dp[i][0] = nums[i];// 初值
            // 就结果
            for (int j = i+1;j < len;j++) {
                    dp[i][j-i] = dp[i][j-i-1] + nums[j];
            }
        }
    }
    
    public int sumRange(int i, int j) {
        return dp[i][j-i];
    }
}

求前缀和，放入map中，区域下标为key

// 相同的思路
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();

public NumArray(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            map.put(Pair.create(i, j), sum);
        }
    }
}

public int sumRange(int i, int j) {
    return map.get(Pair.create(i, j));
}

原地前缀和就行的

// 优化，只用O(n)的空间复杂度
// sum[i] 表示[0,i]的累加和——前缀和
private int[] sum;

public NumArray(int[] nums) {
    sum = new int[nums.length + 1];// 实现原位[i,i]的计算
    for (int i = 0;i< nums.length;i++) {
        sum[i + 1] = sum[i] + nums[i];
    }
}

public int sumRange(int i,int j){
    return sum[j + 1] - sum[i];
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com