arrays - 确定是否存在长度 > 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 整除，因为每隔一个偶数都可以被 4 整除。

收到这样一个列表的概率非常小，并且随着列表变大而继续降低(而且，它适合于数字模式的子集；那些可能会让人感兴趣吗？)，这意味着除非有人煞费苦心地工作要创建一些(如果不是全部的话)大多数现实世界情况会找到一个解决方案，其中包含一个大小为 4 的滑动窗口，该窗口还检查交替奇偶校验。