子矩阵和为k的数量

Question

我刚在编程比赛中遇到了这个问题，但是在规定的时间限制内无法解决。我很好奇正确的方法是什么。任何建议都会有所帮助。

输入 给定一个元素为n（n < 1000）的矩阵a []。 一个整数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个列子集和一个完整的数组，所以总共有5个。

我尝试使用类似于以下链接中的方法进行解决：https://math.stackexchange.com/questions/639172/submatrix-with-sum-k

- Mudit Agarwal

---

我投票关闭此问题，因为它是一个编程竞赛问题的转储。 - tmyklebu

Answer 1

对于子数组和 b[i][j] -> b[i + m][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）的时间复杂度内找到答案。

- Pham Trung

---

完成了..我认为我们也可以减少第二步（找到所有段的总和）的复杂性。 - Mudit Agarwal

@MuditAgarwal 是的，我们只需要检查所有满足条件 k % a == 0 和 a <= square_root(k) 的数字 a，因此检查步骤的时间复杂度为 O(square_root(k))。记得处理正数和负数的情况。 - Pham Trung