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

你的名字 2024-03-26 17:17 41阅读 0赞

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

给定一个整数数组 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 < = n u m s . l e n g t h < = 1 0 4 1 <= nums.length <= 10^4 1<=nums.length<=104
 *   − 1 0 5 < = n u m s \[ i \] < = 1 0 5 -10^5 <= nums\[i\] <= 10^5 −105<=nums\[i\]<=105
 *   0 < = i < = j < n u m s . l e n g t h 0 <= i <= j < nums.length 0<=i<=j<nums.length
 *  最多调用  1 0 4 10^4 104 次 sumRange 方法

#### 思路：(前缀和) ####

根据**数学层面**可以这样理解：  
![在这里插入图片描述][f196a512536f4f0cbf817d85f22c5f35.png]  
**代码理解：** 前缀和数组 sums\[i\]里面存的就是原数组num的**前 i 项和**，例如sums\[2\] 这里面存的就是原数组num的**前2项和**

而数组最大的优点就是便于可以直接根据索引查找，前缀和就是充分运用了数组这个优点，只要理解了前缀和这个概念，代码的思路其实很简单 思路：  
1、首先创建一个前缀和数组int \[\]sums

2、由于前缀和数组sums\[\]里面存的是原数组num的前i项和，故使用其构造方法创建前缀数组sums\[\]时，要引入原数组num\[\]

3、注意创建sums\[\]数组时要注意，数组长度比数组要大一个数组空间，方便数组查询

4、创建完毕后，就直接根据传过来的right和left来对前缀和数组进行查找，注意查找right时注意加一，防止数组下标越界 ， 5、查找到之后，再让两个查找到的数进行相减

6、相减之后的数就返回其值

#### 代码：(Java) ####

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

public class Demo {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int numbers [][] = {
        {
        -2, 0, 3, -5, 2, -1}, {
        0, 2}, {
        2, 5}, {
        0, 5}};
    
    		int sums[] = new int[numbers.length - 1];
    		
    		
    		NumArray numary  = new NumArray(numbers[0]);
    		
    		for(int i = 1; i < numbers.length; i++) {
        
    			sums[i-1] = numary.sumRange(numbers[i][0], numbers[i][1]);
    			
    			System.out.print(sums[i - 1] + " ");
    		}	
    	}
    }

##### 复杂度分析： #####

*  **时间复杂度**：初始化 O(n)，每次检索 O(1)，其中 n 是数组 nums的长度。 初始化需要遍历数组 nums 计算前缀和，时间复杂度是 O(n)。 每次检索只需要得到两个下标处的前缀和，然后计算差值，时间复杂度是 O(1)。
 *  **空间复杂度**：O(n)，其中 n 是数组 nums 的长度。需要创建一个长度为 n+1的前缀和数组。

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[f196a512536f4f0cbf817d85f22c5f35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/62a7731b08614ebb9811efcb34efec11.png
[Link 1]: https://leetcode.cn/problems/range-sum-query-immutable/description/