确定给定数组的任何排列使得长度为 K 的所有子数组之和是否相等

Question

我在一次面试中被问到这个问题。

您将获得一个由 N 个整数组成的数组。您需要确定给定数组是否存在任何排列，以便长度为 K 的所有子数组之和相等。N 可被 K 整除，即 N mod K = 0。
如果数组为 [1，2，1，3，2，3] 且 K = 2，则为 False。
如果数组为 [1，2，1，3，2，3] 且 K = 3，则为 True。

我的逻辑是这样。

1） 如果 N == K，则返回 True。
2） Else 将数组中的每个不同元素存储在字典中。如果字典中不同元素的数量大于 K，则返回 False。
3）否则将每个不同元素的计数存储在字典中。
4） 如果任何非重复元素的计数小于 （N/K），则返回 False。
5） 最后返回 True。

这是我在Python中的代码：

def check(nums, n, k):
if n == k:
    return True
else:
    my_dict = {}
    for i in nums:
        if i not in my_dict:
            my_dict[i] = 1
        else:
            my_dict[i] += 1
    if len(my_dict) > k:
        return False
    count = int(n/k)
    for i,j in my_dict.items():
        if j < count:
            return False
    return True  

我正在做正确的方法吗？有没有更好的方法来做到这一点？

Answer 1

您的解决方案几乎是正确的。问题是，元素计数需要被n / k整除。

让我们假设我们得到了一个符合标准的排列。对于任何不同的元素，很容易观察到，如果它在i处的排列中找到，那么也必须找到它，在：i - k，i - 2k,... ,i mod k和i k，i 2k,.., n - k（i mod k），因此在i处出现意味着在i % k处出现

一个会破坏你的解决方案的例子（几乎肯定是最小的）：

n = 8，k = 4数组= [1，1，1，2，2，2，2，2]