确定给定数组的任何排列是否相等，使得长度为 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(否则将数组中的每个不同元素存储在字典中。如果字典中非重复元素的数量大于 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 < k处发生。现在，在指数低于k的位置上，每个不同的出现都意味着总共出现n / k次(在这里，n mod k = 0是至关重要的事实(。

OP解决方案的反例

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

n = 8， k = 4 数组 = [

1， 1， 1， 2， 2， 2， 2， 2]