找到两个加权平均值相等的子数组
提问于 2012-09-25 12:08:38
我们得到了一个整数数组A。我希望找到两个长度最大的连续子数组(两个子数组的长度必须相等)，它们具有相同的加权平均值。权重是子数组中的位置。例如
A=41111921111119 子阵列：(11119)和(11119)
我试图通过DP找到所有子数组的加权平均值，然后按列排序以找到2，使用相同的length.But，我不能再继续了，我的方法看起来太模糊/粗暴了，我希望得到任何帮助。提前谢谢。
回答 1
Stack Overflow用户
发布于 2012-09-26 07:25:17
首先，由于两个子数组的长度必须相等，所以可以一步一步地考虑从1到n的长度。
对于长度i，可以计算每个子阵的加权和，总复杂度为O(n)。然后对和进行排序，以确定是否有一个相等的对。
因为您排序n次，时间是O(n^2 log n)，而空间是O(n)。
也许我只是重复了问题中提到的你的解决方案？但我觉得它不能再优化了.
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/12590301
复制相关文章
点击加载更多
腾讯云开发者
