确定是否存在一个长度大于1且平均数为整数的连续子数组。

Question

给定一个未排序的整数数组。

我试图想出一个高效的解决方案（优于O(n²)），但我能想到的最好的解决方案是O(n²)：

for i from 0 to size of list:
    sum = list[i]

    for j from i + 1 to size of list:
        sum += list[j]

        if sum % (j - i + 1) == 0:
            return true
return false

我已经阅读了关于滑动窗口技术的内容，但看起来这只对特定长度k的子数组有用。

- user10344418

---

是的，该数组未排序。 - user10344418

看看这个，可能会有所帮助 https://dev59.com/rWvXa4cB1Zd3GeqPFhfc - kuskmen

超过O(n)的算法不可行，你需要读取所有元素！ - user1196549

对不起，比O(n^2)更好。 - user10344418

这是来自在线评测系统的问题吗？如果是的话，能否提供链接？ - fjardon

Answer 1

这可能是一个诡计问题 :) 两个奇数相加得到偶数，两个偶数相加得到偶数。唯一不包括连续子数组长度为2且可被2整除的数据集必须交替出现 [..., 奇数, 偶数, 奇数, 偶数, ...]。但是，数据集需要进一步限制，以防止长度为4的子数组可被4整除，因为每隔一个偶数可被4整除。

接收到这样的列表的概率非常小，并且随着列表变得越来越大而不断减小（而且它适用于数字模式的子集；这些是否有兴趣？），这意味着，除非有人费尽心思地创造一些东西，否则大多数，如果不是所有真实世界的情况都会找到一个大小为4的滑动窗口的解决方案，该方案还检查交替奇偶性。

- גלעד ברקן

---

它的罕见并不意味着不可能。此外，这应该是一条注释，而不是答案。 - orlp

如果你真的声称这是不可能的，那么当然，它就成为了一个答案。但是直到现在你都没有这样声称（你的回答只字未提“极小的概率”），也没有提供任何证据来支持这种说法。 - orlp

@orlp SO的回答并不需要是完整的答案。此外，有关算法在许多数据交互中的表现如何，而不仅仅是一个，的统计显著信息是普遍的（例如在描述排序方法的行为时）。能够对这个问题做出这样的断言是重要和有用的信息。 - גלעד ברקן

我可以证明对于任何大小的列表都存在一个解决方案：只需使用0和1交替的数组。没有子数组具有整数平均值，因为长度大于1的子数组总是具有0 < s < k的和，因此不能被k整除。 - orlp

1, 2, 1, 2, 1, 2, 1, 2, ... 1, 2, 1, 10, 5, 10, 1, 30, 1, 10, ... 1, 2, 5, 6, 5, 6, 5, 14, 9, 42, ... 在每一步中都存在多种可能性，我认为这不会局限于易于检测的模式。 - m69 ''snarky and unwelcoming''