arrays - 和为 k 的子矩阵数

Question

我只是在编程竞赛中遇到了这个问题，无法在规定的时间限制内解决它。所以只是想找到正确的方法。任何建议都会有所帮助。

输入 给定一个有 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) 时间复杂度内找到答案。