和为 k 的子矩阵数

Question

我刚刚在编程竞赛中遇到了这个问题，但无法在规定的时间内解决它 constraints.So 只是想得到正确的 approach.Any 建议会有所帮助。

输入给定一个有 n 个元素的矩阵 a[]，其中 n<1000。整数 k，其中 k<10^9

构造一个新矩阵 b 其中 b[i][j]=a[i]*a[j].

输出总和为 k 的可能子矩阵的数量。

测试用例

a[]={1,-1}
k=0

输出=5 说明

b={ 1,-1,
   -1, 1}

所以 2 个行子集、2 个列子集和 1 个完整数组。所以总共 5.

我试着用这样的方法来解决https://math.stackexchange.com/questions/639172/submatrix-with-sum-k

Answer 1

子数组和b[i][j] -> b[i + m]b[j + n]等于

X =   a[i]*(a[j] + a[j + 1] + ... + a[j + n])
    + a[i + 1]*(a[j] + a[j + 1] + ... + a[j + n])
    + ...
    + a[i + m]*(a[j] + a[j + 1] + ... + a[j + n])
  = sum(a[i] + ..a[i + m])*sum(a[j] +... a[j + n])

因此，任务简化为在数组 a 中找到两个段，它们的和相乘等于 k。

要找到 a 中的所有段总和，可以在 O(n^2).

中完成

将所有的总和存储在HashSet，或者类似的，我们可以在O(n^2)时间复杂度内找到答案。

和为 k 的子矩阵数

Number of submatrix with sum k

arrays

algorithm

data-structures