---
title: "【面试算法笔记】0106-数组-区间和"
source: https://www.zbhgis.com/note/note-20260428-1
author: zbhgis 浩瀚地学
created: 2026-04-28
tags: [面试算法笔记, 算法, LeetCode]
---

> 本文来自浩瀚地学，规范页面（含代码高亮与图片灯箱）：https://www.zbhgis.com/note/note-20260428-1
# 【面试算法笔记】0106-数组-区间和

个人主页：https://github.com/zbhgis

# 前言

本系列主要记录自己学习算法的过程中的感悟。

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

链接：https://leetcode.cn/problems/range-sum-query-immutable/description/

## 注意点

通过计算出前缀和数组，来快速找到对应区间的和。

## 代码

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

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */
```

## 时空复杂度分析

单层循环，需要遍历n次，因此时间复杂度为O(n)

空间复杂度为O(1)

# Acwing795. 前缀和

链接：https://www.acwing.com/problem/content/797/

## 注意点

同上，这一题要注意给出的查询值不是下标。

## 代码

```Java
import java.util.Scanner;

public class Main {
    private static int[] s;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i ++) {
            nums[i] = sc.nextInt();
        }
        s = new int[n + 1];
        for (int i = 0; i < n; i ++) {
            s[i + 1] = s[i] + nums[i];
        }
        for (int i = 0; i < m; i ++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(getRes(l, r));
        }
    }
    
    private static int getRes(int left, int right) {
        return s[right] - s[left - 1];
    }
}
```

## 时间复杂度分析

同上

# 力扣 304.二维区域和检索-矩阵不可变

链接：https://leetcode.cn/problems/range-sum-query-2d-immutable/description/

## 注意点

类似上一题，这回的难点在于怎么构造前缀和，以及二维前缀和如何相减。

最好画个图，前者就是三个小矩形相加，再减去重复部分

后者其实就是大矩形减去一条长边，一条宽边，再加上多减的区域。

## 代码

```Java
class NumMatrix {
    private final int[][] sum;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        sum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */
```

## 时空复杂度分析

双层循环，因此时间复杂度为O(m*n)

空间复杂度为O(1)

# Acwing796. 子矩阵的和

链接：https://www.acwing.com/problem/content/798/

## 注意点

同上，这一题也要注意给出的查询值不是最终下标。

## 代码

```Java
import java.util.Scanner;

public class Main {
    private static int[][] sum;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q = sc.nextInt();
        sum = new int[n + 1][m + 1];
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + sc.nextInt();
            }
        }
        for (int i = 0; i < q; i ++) {
            int row1 = sc.nextInt() - 1;
            int col1 = sc.nextInt() - 1;
            int row2 = sc.nextInt() - 1;
            int col2 = sc.nextInt() - 1;
            System.out.println(getRes(row1, col1, row2, col2));
        }
    }
    private static int getRes(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row2 + 1][col1] - sum[row1][col2 + 1] + sum[row1][col1];
    }
}
```

## 时空复杂度分析

同上

# 参考

https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html