11：0和1个数相同的子数组

:::info 题目：输入一个只包含0和1的数组，请问如何求0和1的个数相同的最长连续子数组的长度？例如，在数组[0，1，0]中有两个子数组包含相同个数的0和1，分别是[0，1]和[1，0]，它们的长度都是2，因此输出2。 :::

  1. public static int findMaxLength(int[] nums) {
  2.     if(nums.length == 0) {
  3.         return 0;
  4.     }
  6.     // 替换所有的0变为-1
  7.     for(int i = 0; i < nums.length; i++) {
  8.         nums[i] = nums[i] == 0 ? -1 : nums[i];
  9.     }
  11.     // key=sum, value=index
  12.     Map<Integer, Integer> sumToIndex = new HashMap<>();
  14.     int sum = 0;
  15.     int maxLength = 0;
  17.     for(int i = 0; i < nums.length; i++) {
  18.         // 当前sum的值
  19.         sum += nums[i];
  21.         // 如果i位置的sum = m， 且存在j位置的sum也为m，那么j-i，就是子数组的长度
  22.         if(sumToIndex.containsKey(sum)) {
  23.             maxLength = Math.max(maxLength, i - sumToIndex.get(sum));
  24.             // 此时也不需要覆盖 sum 这个key，因为覆盖掉，只会让子数组变得更短
  25.         } else {
  26.             sumToIndex.put(sum, i);
  27.         }
  28.     }
  30.     return maxLength;
  31. }

12：左右两边子数组的和相等

:::info 题目：输入一个整数数组，如果一个数字左边的子数组的数字之和等于右边的子数组的数字之和，那么返回该数字的下标。如果存在多个这样的数字，则返回最左边一个数字的下标。如果不存在这样的数字，则返回-1。例如，在数组[1，7，3，6，2，9]中，下标为3的数字（值为6）的左边3个数字1、7、3的和与右边两个数字2和9的和相等，都是11，因此正确的输出值是3。 :::

  1. public static int findPivotIndex(int[] nums) {
  2.     if (nums.length == 0) {
  3.         return -1;
  4.     }
  6.     int total = 0;
  7.     for (int i : nums) {
  8.         total += i;
  9.     }
  11.     int sum = 0;
  12.     int resultIndex = -1;
  14.     for (int i = 0; i < nums.length; i++) {
  15.         if (sum == (total - sum - nums[i])) {
  16.             resultIndex = i;
  17.         }
  18.         sum += nums[i];
  19.     }
  21.     return resultIndex;
  22. }

二维子矩阵的数字之和

:::info 题目：输入一个二维矩阵，如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和？对于同一个二维矩阵，计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如，输入图2.1中的二维矩阵，以及左上角坐标为（2，1）和右下角坐标为（4，3）的子矩阵，该函数输出8。 :::

  1. public static int matrixSum(int[][] nums, int col1, int row1, int col2, int row2) {
  2.         // 1. 计算辅助矩阵(0, 0) 到 (i, j)的点的合
  3.         // 注意此处矩阵的多了一行一列，第一行和第一列都0
  4.         int[][] sum = new int[nums.length + 1][nums[0].length + 1];
  5.         for (int i = 0; i < nums.length; i++) {
  6.             int rowSum = 0;
  7.             for (int j = 0; j < nums[0].length; j++) {
  8.                 rowSum += nums[i][j];
  9.                 sum[i + 1][j + 1] = sum[i][j + 1] + rowSum;
  10.             }
  11.         }
  13.         AlgorithmUtils.printTwoDArray(sum);
  15.         // 计算目标子矩阵的合
  16.         // 注意此处，因为辅助矩阵多了一行一列，所以要在坐标上+1
  17.         return sum[col2 + 1][row2 + 1] - sum[col2 + 1][row1] - sum[col1][row2 + 1] + sum[col1][row1];
  18.     }