🎈202. 快乐数

难度简单1063

编写一个算法来判断一个数 n 是不是快乐数。

[快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

  • 这题目上来就一脸懵逼, 暴力计算肯定就又TLE了, 既然是个简单题, 那应该是有什么小窍门

快乐的知识点增加了 - 快乐数 - 力扣（LeetCode）

链表找环
每个数字都会根据 各位平方和 指向另一个数字，所以从任意数字开始进行 各位平方和 的迭代操作，就相当于在链表上游走。如果 无限循环 但始终变不到 1，那说明肯定是链表游走到了环。

为什么呢？ （此处应该有图）

为什么无限循环就一定是走到了环了呢？而不是链表上的数字越变越大？这里我来给一个证明。

image-20220906215055055

通过上面的证明, 本题也就化为了链表找环问题 ,

  • 快慢指针

slow每次走一步, fast每次走两步,

  • 这里的走步 , 其实就求平方和 ,

当slow==fast的时候, 相当于进入环了,

  • fast超slow整整一个环

返回结果就是slow是否为1

  • 其实本题最后如果slow==fast==1 , 1 本身就是一个环

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isHappy(int n) {
        int slow=n,fast=squareSum(n);
        while(slow!=fast){
            slow=squareSum(slow);
            fast=squareSum(squareSum(fast));
        }
        return slow==1;
    }
    int squareSum(int n){ //求平方和
        int sum=0;
        while(n!=0){
            sum+=(n%10)*(n%10);
            n/=10;
        }
        return sum;
    }
}

🎈287. 寻找重复数

难度中等1880

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

287.寻找重复数 - 寻找重复数 - 力扣（LeetCode）

有一点不太理解:

  • 第二个while循环的作用是什么
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findDuplicate(int[] nums) {
        int slow=nums[0],fast=nums[nums[0]];
        while(slow!=fast){ //这个相遇可能是在环内
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        slow=0;
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
}

61. 旋转链表

难度中等823

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

  • 题目让链表的元素移动, 实际上我们调整链表的指向即可

每个节点向右移动k 个位置, 需要做的操作就是把倒数第k个节点作为头结点, 调整链表

那么我们需要做的操作就是: (在此讨论一般情况)

  1. 断开倒数第k个 节点与前面的节点
  2. 使末尾结点指向头结点
  3. 返回倒数第k个节点即可

代码如下

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
class Solution {
    public ListNode rotateRight(ListNode head, int k) { // 从倒数第k个节点断开, 然后链接首尾节点
        if(head==null||head.next==null) return head;
        ListNode tail=null,cur=head,res=null,pre = null; //tail 尾结点  pre: 倒数第k个节点的前置节点 res:倒数第k个节点
        int cnt=0; //统计节点总数
        while (cur!=null){// 遍历: 获取尾结点, 获取节点的总个数
            cnt++;
            if(cur.next==null) tail=cur;
            cur=cur.next;
        }
        k%=cnt;//注意k 可能会大于链表的长度, 因此需要取模
        if(k==0) return head; // 不需要移动节点, 直接return head
        tail.next=head;
        cur=head;
        for (int i = 0; i <= cnt-k; i++) {// 断开节点操作
            if(i==cnt-k-1)
                pre=cur;
            if(i==cnt-k){
                res=cur;
            }
            cur=cur.next;
        }
        pre.next=null;   
        return res;
    }
}

4. 寻找两个正序数组的中位数

难度困难5828

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

暴力解法

  • 遍历两个数组, 每次选择较小的那个添加, 最后返回中位数即可

不符合题目的要求, 正确的做法应该是二分(题目提示了 算法的时间复杂度应该为 O(log (m+n)))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double[]nums=new double[nums1.length+ nums2.length];
        int i=0,p1=0,p2=0;
        while(i<nums.length&&p1<nums1.length&&p2<nums2.length){
            nums[i++]=nums1[p1]<nums2[p2]?nums1[p1++]:nums2[p2++];
        }
        while(i<nums.length&&p1<nums1.length){
            nums[i++]=nums1[p1++];
        }
        while(i<nums.length&&p2<nums2.length){
            nums[i++]=nums2[p2++];
        }
        return nums.length%2==0? (nums[nums.length/2]+nums[nums.length/2-1])/2:nums[nums.length/2];
    }
}

二分解法:

  • 题目给的是正序数组, 因此可以考虑使用二分解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        double[]nums=new double[nums1.length+ nums2.length];
        int i=0,p1=0,p2=0;
        while(i<nums.length&&p1<nums1.length&&p2<nums2.length){
            nums[i++]=nums1[p1]<nums2[p2]?nums1[p1++]:nums2[p2++];
        }
        while(i<nums.length&&p1<nums1.length){
            nums[i++]=nums1[p1++];
        }
        while(i<nums.length&&p2<nums2.length){
            nums[i++]=nums2[p2++];
        }
        return nums.length%2==0? (nums[nums.length/2]+nums[nums.length/2-1])/2:nums[nums.length/2];
    }
}

152. 乘积最大子数组 :DP

难度中等1782

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

  • 遍历数组时计算当前最大值，不断更新
  • 令imax为当前最大值，则当前最大值为 imax = max(imax * nums[i], nums[i])
  • 由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin，imin = min(imin * nums[i], nums[i])
  • 当负数出现时则imax与imin进行交换再进行下一步计算
  • 时间复杂度：O(n)

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE, imax = 1, imin = 1;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0){ 
              int tmp = imax;
              imax = imin;
              imin = tmp;
            }
            imax = Math.max(imax*nums[i], nums[i]);
            imin = Math.min(imin*nums[i], nums[i]);
            
            max = Math.max(max, imax);
        }
        return max;
    }
}

🌲105. 从前序与中序遍历序列构造二叉树

labuladong 题解思路

难度中等1724

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {//前序:   3 9 20 15 7 中序: 9 3 15 20 7
/*前序遍历的第一个节点就是根节点, 需要通过中序遍历来判断当前的子树是否结束
*/
    int preIdx=0;
    int inIdx=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(null,preorder,inorder);
    }
    TreeNode dfs(TreeNode finish,int[]preorder,int[]inorder){
        if(preIdx>=preorder.length||(finish!=null&&inorder[inIdx]==finish.val))
            return null;// 遍历完了
        TreeNode root=new TreeNode(preorder[preIdx++]);
        root.left=dfs(root,preorder,inorder);
        inIdx++;
        root.right=dfs(finish,preorder,inorder);
        return root;
    }
}

🌲889. 根据前序和后序遍历构造二叉树

labuladong 题解思路

难度中等275

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

1
2
3
4
5
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {

    }
}

🌲106. 从中序与后序遍历序列构造二叉树

labuladong 题解思路

难度中等835

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

1
2
3
4
5
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {

    }
}

120. 三角形最小路径和 :DP

思路

难度中等1101

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1

本题需要用到自底向上DP

二维数组解法 :

  • 便于理解

由于题目给的三角形的特殊性, 自底向上的最终目标一定是顶点

  1. dp数组 : dp[i][j] 表示的是 从最后一行到第i 行的[j]位置最短路径 ,

  2. 状态转移 : 从最后一行走到当前行的最短路径 = 当前元素在下一行的相邻元素的较小值

    状态转移方程为: dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j)

  3. dp数组初始化: 初始化数组的规模为 new int[n+1][n+1] , 防止越界, 在计算最后一层的时候由于多了一层0 ,所以不用担心会多算的问题

  4. 遍历范围以及方向:

    • 范围 : 纵向: [n-1,0] , 横向: [0,i]
    • 方向 :自底向上遍历, 反向求出最小的路径

  5. 返回结果, return dp[0][0]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {  //这个 list 就是个二维数组
        int n =triangle.size(); // 表示行数
        int [][]dp =new int[n+1][n+1];
        for(int i=n-1;i>=0;i--){// 自底向上DP , 通过dp数组的下一行的元素与当前的list中的元素累加,最终得到dp[0][0]    
            for (int j = 0; j <=i ; j++) {
                dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}

一维数组解法

  • 我们在状态转移的过程中发现当前的元素只与上一层的元素有关, 之前的元素的空间相当于都浪费了, 因此可以选择直接覆盖上一层的结果

    将空间复杂度由 O(n2) 降低至O(n)

思路与二维数组的思路是完全相同的, 只是优化写法

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minimumTotal(List<List<Integer>> list) {  //这个 list 就是个二维数组
        int n=list.size();
        int[]dp=new int[n+1]; //dp[i] 表示的是第i 层的最小路径
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <=i ; j++) {
                dp[j]=list.get(i).get(j)+Math.min(dp[j],dp[j+1]); // 当前层的最小路径 
            }
        }
        return dp[0]; // 自底向上 DP , 最终返回dp[0]
    }
}

655. 输出二叉树

本题需要注意题目给的提示

难度中等202

给你一棵二叉树的根节点 root ，请你构造一个下标从 0 开始、大小为 m x n 的字符串矩阵 res ，用以表示树的 格式化布局 。构造此格式化布局矩阵需要遵循以下规则：

  • 树的 高度 为 height ，矩阵的行数 m 应该等于 height + 1 。
  • 矩阵的列数 n 应该等于 2height+1 - 1 。
  • 根节点 需要放置在 顶行 的 正中间 ，对应位置为 res[0][(n-1)/2] 。
  • 对于放置在矩阵中的每个节点，设对应位置为 res[r][c] ，将其左子节点放置在 res[r+1][c-2height-r-1] ，右子节点放置在 res[r+1][c+2height-r-1] 。
  • 继续这一过程，直到树中的所有节点都妥善放置。
  • 任意空单元格都应该包含空字符串 "" 。

返回构造得到的矩阵 res 。

根据题目的提示, 可以想到先用二维数组来操作元素, 然后再将其存入List中

步骤

  1. 通过int depth(TreeNode root ) 求出二叉树的深度与宽度

    这里视 单个节点的高度为1

    height=depth(root) , wide= Math.pow(2,height)-1;

  2. 初始化矩阵,

    • 初始化矩阵的大小

      注意这里矩阵的规格与二叉树的高度宽度的关系 : m=hegiht ,n=Math.pow(2,m)-1

    • 填充元素 : 利用Arrays.fill()

  3. 递归填充矩阵

    • matrix[0][(n-1)/2]=String.valueOf(root.val);

    • 根据题目的提示 分别递归左右孩子即可

      dfs(root.right,r+1, (int) (c+Math.pow(2,m-2-r)));

      dfs(root.left,r+1, (int) (c-Math.pow(2,m-2-r)));

  4. 将矩阵的元素复制到List并返回

注意Arrays.fill() 不能直接填充二维矩阵

代码如下

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
class Solution {
    String[][]matrix;
    int m,n; // 分别表示二叉树的深度以及宽度  n=pow(2,m)-1; 依照题意: m=height+1 n=2^(height+1) -1
    public List<List<String>> printTree(TreeNode root) {
        m=depth(root); // 先求出 二叉树的深度 , 通过树的深度 求出宽度 len= pow(2,depth)-1 ;
        n= (int) (Math.pow(2,m)-1);
        matrix=new String[m][n];
        for (String[] strings : matrix) {
            Arrays.fill(strings,"");// 先填充好所有的位置为 空字符串 , 然后修改相应位置的元素即可
        }
//        
        dfs(root,0,(n-1)/2);
        List<List<String>> res=new ArrayList<>();
        for (String[] strings : matrix) {
            List<String> track=new ArrayList<>();
            for(String s:strings){
                track.add(s);
            }
            res.add(track);
        }
        return res;
    }
    void dfs(TreeNode root,int r,int c){// 递归填充矩阵
        if(root==null||r>=m||c>=n) return; // 节点为空或者 越界 就return
        matrix[r][c]= String.valueOf(root.val);
        dfs(root.left,r+1, (int) (c-Math.pow(2,m-2-r)));
        dfs(root.right,r+1, (int) (c+Math.pow(2,m-2-r)));
    }
    int depth(TreeNode root){
        if(root==null) return 0;
        return Math.max(depth(root.left),depth(root.right))+1;
    }
}

1567. 乘积为正数的最长子数组长度:DP

难度中等177

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。

一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。

请你返回乘积为正数的最长子数组长度。

  1. dp数组定义: 定义两个规模与nums 相当的数组

    pos[i]表示下标为0~i的元素的乘积为 正数的子数组的长度
    neg[i]表示下标为0~i的元素的乘积为 负数的子数组的长度

  2. 状态转移: 对于当前的nums[i]

    • nums[i]>0 :

      pos[i]=pos[i-1]+1; 正数直接就是之前的长度+1
      neg[i]=neg[i-1]>0?neg[i-1]+1:0; // 负数乘以一个正数还是负数

    • nums[i]=0 : pos[i]=0; neg[i]=0; 0直接截断之前的数组

    • nums[i]<0 :

      如果之前的负数子数组的最大长度不小于0 , 那么正数序列就是 负数子数组+1 ,否则为0

      负数序列的长度= 之前的正数序列的长度+1

  3. dp数组初始化:

  • 初始化pos[] ,neg[] , 回顾dp数组的定义, 可以得出初始化方式为

    pos[i]=nums[i]>0?1:0; neg[i]=nums[i]<0?1:0;

  1. 返回值: 在dp的过程中维护res , 作为乘积为正数的最长的子数组的规模 ,最后返回即可

代码如下

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
class Solution {
    public int getMaxLen(int[] nums) {
        int[]pos=new int[nums.length];// pos[i]表示下标为0~i的元素的乘积为 正数的子数组的长度
        int[]neg=new int[nums.length];// neg[i]表示下标为0~i的元素的乘积为 负数的子数组的长度
        for (int i = 0; i < nums.length; i++) {
            pos[i]=nums[i]>0?1:0;
            neg[i]=nums[i]<0?1:0;
        }
        int res=pos[0];
        for (int i = 1; i < nums.length; i++) {
            if(nums[i]>0){
                pos[i]=pos[i-1]+1;
                neg[i]=neg[i-1]>0?neg[i-1]+1:0; // 负数乘以一个正数还是负数
            }else if(nums[i]==0){
                pos[i]=0;
                neg[i]=0;
            }else{ //nums[i] < 0
                pos[i]=neg[i-1]>0?neg[i-1]+1:0; // 如果之前的负数序列的长度不为0 , 那么正数序列就 +1 ,否则为0
                neg[i]=pos[i-1]+1; // 负数序列的长度= 之前的正数序列的长度+1
            }
            res=Math.max(res,pos[i]);
        }
        return res;
    }
}

740. 删除并获得点数 : DP

难度中等675

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

本题的精髓是把题目转换成打家劫舍的问题

  • 在偷了三处村庄后这个小偷有来到了第四个村庄进行偷窃。他发现这个村庄得居民变得聪明了，将房屋打乱了顺序，并且报警器也变得更加得灵敏，在偷了5块钱后，偷6块钱跟4块钱它都会报警，但是由于性能的提升，报警器也有"bug", 那就是偷了5块钱后继续偷5块钱 报警器不会触发。这小偷还是个程序员呢！"

话不多说, 直接上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int deleteAndEarn(int[] nums) {
        // 将 每个值 都存储起来,那么如果我们使用了trans[i] , 那么就不能使用 trans[i-1] 以及trans[i+1]
        int[]trans=new int[10001];
        for (int num : nums) {
            trans[num] += num;
        }
        int[]dp=new int[trans.length+1];//dp[i]表示前i 个房间的最大的抢劫的金额
        //状态转移: dp[i]= Math.max(dp[i-1],trans[i]+dp[i-2])
        dp[0]=0;
        dp[1]=trans[0];
        int res=dp[0];
        for (int i = 2; i < dp.length; i++) {
            dp[i]=Math.max(dp[i-1],trans[i-1]+dp[i-2]);
        }
        return dp[dp.length-1];
    }
}

918. 环形子数组的最大和 :DP

难度中等404

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

思路:

我花一遍就看懂的题解，你也可以！ - 环形子数组的最大和 - 力扣（LeetCode）

题目相较于53. 最大子数组和 - 力扣（LeetCode）, 也就是多了一种情况:

第一种情况：这个子数组不是环状的，就是说首尾不相连。
第二种情况：这个子数组一部分在首部，一部分在尾部，我们可以将这第二种情况转换成第一种情况

所以这最大的环形子数组和 = max(最大子数组和，数组总和-最小子数组和)

**证明如下: **

证明一下第二种情况（最大子数组是环形的）
max(前缀数组+后缀数组)
= max(数组总和 - subarray) subarray指的是前缀数组和后缀数组中间的数组
= 数组总和 + max(-subarray) 数组总和是不变的，直接提出来

​ = 数组总和 - min(subarry) 。。。这个都懂吧，把负号提出来，max变成min

极端情况：

  • 如果说这数组的所有数都是负数，那么上面的公式还需要变一下，*
  • *因为这种情况，对于上面的第一种情况sum会等于数组中的最大值，
  • 而对二种情况sum=0（最小的子数组就是本数组，total-total=0）。
  • 所以多加一个case，判断最大子数组和是否小于0，小于0，直接返回该maxSubArray
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
  public int maxSubarraySumCircular(int[] A) {
        int total = 0, maxSum = A[0], curMax = 0, minSum = A[0], curMin = 0;
        for (int a : A) {
            curMax = Math.max(curMax + a, a);
            maxSum = Math.max(maxSum, curMax);
            curMin = Math.min(curMin + a, a);
            minSum = Math.min(minSum, curMin);
            total += a;
        }
        return maxSum > 0 ? Math.max(maxSum, total - minSum) : maxSum;
    }
}

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

难度中等432

给定一个二维矩阵 matrix，以下类型的多个请求：

  • 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

暴力解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class NumMatrix {
    int[][]matrix;
    int m,n;
    public NumMatrix(int[][] matrix) {
        this.matrix=matrix;
        m=matrix.length;
        n=matrix[0].length;
    }
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res=0;
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                res+=matrix[i][j];
            }
        }
        return res;
    }
}

前缀和

如何求二维的前缀和，以及用前缀和求子矩形的面积 - 二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）

  • 这道题是「303. 区域和检索 - 数组不可变」的进阶，要求计算子矩阵的元素和。

  • 使用prefixSum[i][j] 存储 (0,0)~(i,j) 位置的和, 需要计算的时候直接计算即可

预计算整个矩阵的前缀和矩阵, 实现 O(1)时间的查询

步骤一：求 preSum

我们定义 preSum[i][j] 表示 从[0,0] 位置到[i,j] 位置的子矩形所有元素之和。

减去 S(O, A)的原因是 S(O,C) 和S(O,B) 中都有 S(O,A)，即加了两次S(O,A)，所以需要减去一次 S(O, A)。

求prefixSum[i][j] 的递推公式如下

preSum[i][j]=preSums[i−1][j]+preSum[i][j−1]−preSum[i−1][j−1]+matrix[i][j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumMatrix {
    int[][] prefixSum;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        prefixSum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i + 1][j + 1] = prefixSum[i][j + 1] + prefixSum[i + 1][j] - prefixSum[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row1][col2 + 1] - prefixSum[row2 + 1][col1] + prefixSum[row1][col1];
    }
}