arrays - 了解三元组计数 HackerRank

Question

我一直在应对这个挑战: Count Triplets ，经过大量的努力，我的算法并没有适用于每个测试用例。

由于在讨论中，我看到了一段代码并试图找出代码的真正功能，但我仍然无法理解这段代码是如何工作的。

解:

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)
v3 = defaultdict(int)
count = 0
for k in arr:
    count += v3[k]
    v3[k*r] += v2[k]
    v2[k*r] += 1
print(count)

上面的代码完美地适用于每个测试用例。我已经测试了 k 、 v2 、 v3 的值来理解，但仍然不明白代码如何在计数三元组中如此流畅地工作。我也无法在梦中想到那个解决方案。我想知道人们如何如此聪明地制定出这个解决方案。尽管如此，如果我能得到正确的解释，我会很高兴。谢谢

k,v2,v3 的输出

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)
v3 = defaultdict(int)
count = 0
for k in arr:
    count += v3[k]
    v3[k*r] += v2[k]
    v2[k*r] += 1
    print(k, count, v2, v3)

输出

1 0 defaultdict(<class 'int'>, {1: 0, 3: 1}) defaultdict(<class 'int'>, {1: 0, 3: 0})                                                  
3 0 defaultdict(<class 'int'>, {1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {1: 0, 3: 0, 9: 1})                                      
9 1 defaultdict(<class 'int'>, {27: 1, 1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {27: 1, 1: 0, 3: 0, 9: 1})                        
9 2 defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 1, 9: 1}) defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 0, 9: 1})                        
27 4 defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 1, 81: 1, 9: 1}) defaultdict(<class 'int'>, {27: 2, 1: 0, 3: 0, 81: 2, 9: 1})         
81 6 defaultdict(<class 'int'>, {1: 0, 3: 1, 243: 1, 81: 1, 9: 1, 27: 2}) defaultdict(<class 'int'>, {1: 0, 3: 0, 243: 1, 81: 2, 9: 1, 
27: 2})

Answer 1

因此，代码在遍历数组时会跟踪潜在的对和三元组。

For each value in the array:
    // Increment count by the number of triplets that end with k
    count += v3[k]
    // Increment the number of potential triplets that will end with k*r
    v3[k*r] += v2[k]
    // Increment the number of potential pairs that end with k*r
    v2[k*r] += 1  

任何给定 k 的三元组数是到目前为止我们遇到的任何给定 k/r 的对数。
请注意，在整个循环中，v3[k] 和 v2[k] 通常为零，直到它们达到我们在前一次迭代中预测的 k*r 值。