leetcode-1074-元素和为目标值的子矩阵数量

[题目描述]

  1. //给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。 
  2. //
  3. // 子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。 
  4. //
  5. //
  6. // 如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵
  7. //也不同。 
  8. //
  9. // 
  10. //
  11. // 示例 1： 
  12. //
  13. // 
  14. //
  15. // 
  16. //输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
  17. //输出：4
  18. //解释：四个只含 0 的 1x1 子矩阵。
  19. // 
  20. //
  21. // 示例 2： 
  22. //
  23. // 
  24. //输入：matrix = [[1,-1],[-1,1]], target = 0
  25. //输出：5
  26. //解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。
  27. // 
  28. //
  29. // 示例 3： 
  30. //
  31. // 
  32. //输入：matrix = [[904]], target = 0
  33. //输出：0
  34. // 
  35. //
  36. // 
  37. //
  38. // 提示： 
  39. //
  40. // 
  41. // 1 <= matrix.length <= 100 
  42. // 1 <= matrix[0].length <= 100 
  43. // -1000 <= matrix[i] <= 1000 
  44. // -10^8 <= target <= 10^8 
  45. // 
  46. // Related Topics 数组 动态规划 Sliding Window 
  47. // 👍 121 👎 0

[题目链接]

leetcode题目链接

[github地址]

代码链接

[思路介绍]

思路一: 暴力法（枚举上下边界，方便理解）

  • 求出每个矩阵的和，然后返回target矩阵
  • 这种m m n * n 应该是一定会超时的（居然没超时）
  • 核心关键在于subArray函数确定连续子列和为target 是n * n 还是n
  1. public int numSubmatrixSumTarget(int[][] matrix, int target) {
  2.     //corner case
  3.     //本题限制了 matrix的极限状态 可以不考虑边界值
  4.     int m = matrix.length, n = matrix[0].length, res = 0;
  5.     for (int i = 0; i < m; i++) {
  6.         //上下边界每列和的数组
  7.         int[] sum = new int[n];
  8.         for (int j = i; j < m; j++) {
  9.             for (int k = 0; k < n; k++) {
  10.                 //每列求和
  11.                 sum[k] += matrix[j][k];
  12.             }
  13.             //求连续子数组和是否为target
  14.             res += subArray(sum, target);
  15.         }
  16.     }
  17.     return res;
  18. }
  19. //按照思路1就是直接暴力
  20. //我属实没太看懂为啥这没TLE
  21. private int subArray(int[] sum, int target){
  22.             int res = 0;
  23.             for (int i = 0; i < sum.length; i++){
  24.                 int temp = 0;
  25.                 for (int j = i; j < sum.length; j++){
  26.                     temp += sum[j];
  27.                     if (temp == target){
  28.                         res +=1;
  29.                     }
  30.                 }
  31.             }
  32.             return res;
  33. }

**时间复杂度：O(m m n n)

思路二: 暴力法的优化

  • subArray使用hashmap进行处理，类似两数之和的设计，map容斥原则
  • 相关题目链接 leetcode-1 leetcode-560
  • 站内博客导航 每日一题系列
public int numSubmatrixSumTarget(int[][] matrix, int target) {
    //corner case
    //本题限制了 matrix的极限状态 可以不考虑边界值
    int m = matrix.length, n = matrix[0].length, res = 0;
    for (int i = 0; i < m; i++) {
        //上下边界每列和的数组
        int[] sum = new int[n];
        for (int j = i; j < m; j++) {
            for (int k = 0; k < n; k++) {
                //每列求和
                sum[k] += matrix[j][k];
            }
            //求连续子数组和是否为target
            res += subArray(sum, target);
        }
    }
    return res;
}
private int subArray(int[] sum, int target){
            Map<Integer, Integer> map = new HashMap<>();
            //防止 nums[0] == k的时候没有算到
            //因为先更新res，后更新map，所以不会重复计算
            map.put(0,1);
            int res = 0, n = sum.length,tempSum = 0;
            for (int num: sum
                 ) {
                tempSum += num;
                if (map.containsKey(tempSum - target)){
                    res += map.get(tempSum - target);
                }
                //互斥原则，找到排除前缀后剩余和为target的子数组
                map.put(tempSum, map.getOrDefault(tempSum,0) + 1);
            }
            return res;
}

时间复杂度：O(m m n)