包含至少 k 对重复项的连续子数组的数量

Question

我刚刚参加面试，被问到这个问题： 给定一个数组编号和一个正整数 k，计算包含至少 k 对重复项的连续子数组的数量 这是我想出的解决方案，它肯定错过了一些边缘情况：

from collections import Counter

def solution(numbers, k):
    # for a subarray to contain at least k pairs of duplicates the subarray must be at least size 2k
    start, count, array_count = 0, 0, 0
    window_size = 2*k
    freq_map = Counter(numbers[:window_size])

    # check if in the initial window, any element has a freq greater than 1
    for _, frequency in freq_map.items():
        if frequency > 1:
            count += 1

    for num in numbers[window_size:]:
        freq_map[num] += 1
        if freq_map[num] >= 2:
            count += 1

        if count >= k:
            array_count += 1
            if freq_map[numbers[start]]:
                freq_map[numbers[start]] -= 1
                if freq_map[numbers[start]] < 2:
                    count -= 1
            start += 1  # slide starting point of window

    return array_count

事实是，我认为我满足所有测试用例，除非整个数组包含在结果中。这让我相信最佳解决方案不是滑动窗口解决方案。例如

numbers = [2,2,2,2,2,2]  k = 3

或

numbers = [0,1,0,1,0]  k = 2

我也知道我错过了初始窗口中可能存在有效子数组的情况。

我希望看到更多最佳解决方案，以便我可以学习（最好可以用滑动窗口解决，哈哈）。

为了让一切都清晰可见，面试官期望

[2,2,2,2,2,2]  k=3

的答案为 1，因为只有 1 个子数组至少有 3 对重复项（2 个）`

Answer 1

这似乎太简单了，这让我担心我误解了这个问题。

红宝石：

def kpairs(arr, k)
  nsubarrays = 0
  h = Hash.new(0)
  arr.each do |x|
    h[x] += 1
    if h.sum { |k,v| v/2 }
      nsubarrays += 1
      h = Hash.new(0)
    end
  end
  nsubarrays
end 

---

arr = [2,2,2,2,2,2]
kpairs(arr, 3)

arr = [2,2,2,2,2,2,2]
kpairs(arr, 3)

arr = [3, 0, 3, 0, 1, 2, 2, 3, 0, 3, 3, 0, 0,
       0, 1, 1, 0, 1, 3, 1, 3, 1, 2, 1, 1]
kpairs(arr, 2) #=> 4
kpairs(arr, 3) #=> 3
kpairs(arr, 4) #=> 2

---

h = Hash.new(0)

创建一个“默认值”为零的（“计数”）哈希值。假设

h = { 1=>2, 4=>1, 2=>3 }

这意味着，到目前为止，当前正在处理的子数组有

2

1

、

1

4

和

3

2

。然后

h.sum { |k,v| v/2 } #=> 2

计算对的数量。 “块”

{...}

枚举了哈希的每个键值对

k,v

。如果

2 < k

我们检查数组的下一个元素。假设它是

1

。然后我们执行

h[1] += 1 #=> { 1=>3, 4=>1, 2=>3 }

但是

h.sum { |k,v| v/2 } #=> 2

不变。

h[1] += 1

可以读取

h[1] = h[1] + 1

。

如果数组中的下一个元素是

3

h[3] += 1 #=> { 1=>3, 4=>1, 2=>3, 3=>1 }

由于

h

没有键

3

，因此

h[3]

右侧的

h[1] = h[1] + 1

被指定为“默认值”，即零。

一旦

h.sum { |k,v| v/2 }

等于

k

，变量

subarrays

就会加一，并且哈希值

h

会重新初始化为

Hash.new(0)

。