确定是否存在长度> 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的子阵列非常有用.

Answer 1

这可能是一个棘手的问题:)两个奇数之和为偶数，两个偶数之和为偶数。唯一不包含长度为 2 且可被 2 整除的连续子数组的数据集必须交替[..., odd, even, odd, even, ...]. 但随后需要进一步限制数据集，以防止长度为 4 的子数组被四整除，因为所有其他偶数都可以被四整除。

收到这样一个列表的概率非常小，并且随着列表变大而继续减少（更重要的是，它适合于数字模式的子集；这些模式会引起兴趣吗？），这意味着除非有人煞费苦心地创建一些，大多数（如果不是全部）现实世界的情况都会找到一个具有大小为 4 的滑动窗口的解决方案，该窗口还检查交替奇偶校验。