总和等于 k 的方子矩阵
给定数字和数字k的2D矩阵，请查找是否存在 square submatrix ，总和等于k 。
我尝试了使用TC O（n^3）的DP方法，并使用二进制搜索进行了优化以获取TC O（n log n）。
有没有办法做到这一点是 o（n*n）？
Given a 2D matrix of numbers and a number K, find if there exists a square submatrix with sum equal to K.
I have tried the DP approach with TC O(n^3) and optimised it using binary search to get TC O (n log n).
https://www.geeksforgeeks.org/maximum-size-square-sub-matrix-with-sum-less-than-or-equals-to-k/
Is there a way to do this is O(n*n) ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我在编码挑战网站上看到了一个类似的问题 cses （如果发现问题链接，我会在此处附加它）。
我不会给您答案，而是一个通用的方向，请尝试研究
前缀总和数组。这是链接与说明和使用。
您可以使用此概念在O（n^2）时间和O（n^2）空间复杂性中解决此问题。
I saw a similar question on the coding challenges site CSES (If ill find the question link I will attach it here).
I won't give you the answer but a general direction, try to research about
prefixes sum array.here is a link to an explanation and use.
You can use this concept to solve this problem in O(n^2) time and O(n^2) space complexity.