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

/*
 * Approach using Java Streams:
 * 1. Iterate over all possible pairs of rows.
 * 2. For each pair of rows, compute the sum of elements between the rows for each column.
 * 3. Use a HashMap to store the prefix sums and count the number of submatrices that sum up to the target.
 */
import java.util.HashMap;
import java.util.stream.IntStream;

public class SubmatrixSumStream {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        int result = 0;

        for (int r1 = 0; r1 < rows; r1++) {
            int[] colSum = new int[cols];
            for (int r2 = r1; r2 < rows; r2++) {
                IntStream.range(0, cols).forEach(c -> colSum[c] += matrix[r2][c]);
                result += countSubarraysWithSum(colSum, target);
            }
        }

        return result;
    }

    private int countSubarraysWithSum(int[] arr, int target) {
        HashMap<Integer, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0, 1);
        int sum = 0;
        int count = 0;

        for (int num : arr) {
            sum += num;
            if (prefixSumMap.containsKey(sum - target)) {
                count += prefixSumMap.get(sum - target);
            }
            prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0) + 1);
        }

        return count;
    }
}