1.问题

该函数有两个参数，即：

• arr：整数数组
• r：整数，公比

输入可以是

arr: [1, 2, 2, 4]
r: 2

目标是返回构成等比级数的三胞胎的计数。

2.如何解决

解决这个问题的方法有很多，比如在comment from RobertsN的基础上，从SagunB

• 时间复杂度O（n）-〉
• 不需要除法，只需要乘以R
• 使用map（C++）或dict（Java，Python）是必须的-〉可以是无序的map（节省O（logN））
• 在阅读一个值的时候试着向前看-〉这个值以后会成为一个三元组的一部分吗？
• 无需将（R == 1）视为极端情况

from collections import Counter

# Complete the countTriplets function below.
def countTriplets(arr, r):
    r2 = Counter()
    r3 = Counter()
    count = 0
    
    for v in arr:
        if v in r3:
            count += r3[v]
        
        if v in r2:
            r3[v*r] += r2[v]
        
        r2[v*r] += 1

    return count

或者像你说的

from collections import defaultdict

# Complete the countTriplets function below.
def countTriplets(arr, r):
    v2 = defaultdict(int)
    v3 = defaultdict(int)
    count = 0
    for k in arr:
        count += v3[k]
        v3[k*r] += v2[k]
        v2[k*r] += 1
    return count

3.最终结果

两个用例都将通过HackerRank中的所有当前13个测试用例

4.解释您的案例

RobertsN的注解很好地解释了你的代码（和你的代码很相似），不过，为了更好地理解代码是如何工作的，只需要打印出count、v2和v3的情况。
假设你的输入是

4 2
1 2 2 4

预期输出为

2

同样，我们知道根据定义，v2和v3看起来都像

defaultdict(<class 'int'>, {})

这就留下了for循环来理解。可能会引起一些混乱的是运算符+=，但那是already addressed by me in another answer。
现在，为了理解剩下的部分，我们可以将循环改为

for k in arr:
    print(f"Looping...")
    print(f"k: {k}")
    print(f"v3_before_count: {v3}")
    count += v3[k]
    print(f"count: {count}")
    print(f"k*r: {k*r}")
    print(f"v3_before: {v3}")
    v3[k*r] += v2[k]
    print(f"v3[k*r]: {v3[k*r]}")
    print(f"v2[k]: {v2[k]}")
    print(f"v3_after: {v3}")
    print(f"v2_before: {v2}")
    v2[k*r] += 1
    print(f"v2_after: {v2}")
    print(f"v2[k*r]: {v2[k*r]}")

会让你看到

Looping...
k: 1
v3_before_count: defaultdict(<class 'int'>, {})
count: 0
k*r: 2
v3_before: defaultdict(<class 'int'>, {1: 0})
v2_before_v3: defaultdict(<class 'int'>, {1: 0})
v3[k*r]: 0
v2[k]: 0
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0})
v2_before: defaultdict(<class 'int'>, {1: 0})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1})
v2[k*r]: 1
Looping...
k: 2
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0})
count: 0
k*r: 4
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0})
v3[k*r]: 1
v2[k]: 1
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 1})
v2[k*r]: 1
Looping...
k: 2
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
count: 0
k*r: 4
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 1})
v3[k*r]: 2
v2[k]: 1
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 1})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2})
v2[k*r]: 2
Looping...
k: 4
v3_before_count: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
count: 2
k*r: 8
v3_before: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v2_before_v3: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2})
v3[k*r]: 2
v2[k]: 2
v3_after: defaultdict(<class 'int'>, {1: 0, 2: 0, 4: 2, 8: 2})
v2_before: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2})
v2_after: defaultdict(<class 'int'>, {1: 0, 2: 1, 4: 2, 8: 1})
v2[k*r]: 1

提取出想要的信息。我们能从中观察到什么呢？

• 计数在最后一个循环中从0增加到2。
• k遍历arr的所有值，所以它是1，2，2和4
• 在初始循环中，v3_before_count为{}，v3_before为{1：0}
• 等等。

最有可能的是，这个过程会引出问题，回答这些问题会让你更接近于理解它。

所以当代码遍历数组时，它会跟踪潜在的对和对。

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值。

我一直在努力理解它，最后，这段C#代码应该很容易理解

static long countTriplets(List<long> arr, long r)
{
    //number of times we encounter key*r
    var doubles = new Dictionary<long, long>();
    //number of times we encounter a triplet
    var triplets = new Dictionary<long, long>();
    long count = 0;
    foreach (var key in arr)
    {
        long keyXr = key * r;

        if (triplets.ContainsKey(key))
            count += triplets[key];

        if (doubles.ContainsKey(key))
        {
            if (triplets.ContainsKey(keyXr))
                triplets[keyXr] += doubles[key];
            else
                triplets.Add(keyXr, doubles[key]);
        }

        if (doubles.ContainsKey(keyXr))
            doubles[keyXr]++;
        else
            doubles.Add(keyXr, 1);
    }
    return count;
}

from collections import defaultdict

arr = [1,3,9,9,27,81]
r = 3
v2 = defaultdict(int)   #if miss get 0
v3 = defaultdict(int)   #if miss get 0 
count = 0`enter code here`
for k in arr:
    #updating the count, starts propagating with delay=2 elements
    count += v3[k]

    # number of triplets with last component ending
    # on index i of k in array
    v3[k*r] += v2[k]

    # number of pairs with last component ending
    # on index i of k in array
    v2[k*r] += 1
print(count)

最好通过例子来理解--假设我们有数组11111，并且i=3，所以111〉1〈1。
V2当前具有计数111，11〉1存在两个以〉1结束的对，对于长度（数组）=n，通常为n-1。
现在在v3，我们从v2递归地构造count，如下所示：对于创建的和用v2计数的每个对，我们指定最后一个分量，对于#pairs = n，存在n个这样的选项。
因此，对于i=3：

11.1 (v2=1) //this pair remains by sum
+
.111 (v2=2) //these are new
1.11 (v2=2)

希望这有帮助！

数字X的潜在值：存在的三元组的数目（如果有的话）使用X作为完全形成三元组的优先级。
让我们举一个例子：1 2 4与r = 2的关系。
S1：带有1：没有三元组，因为1/2=0.5和1/2/2=0.25不可用。请在散列表中添加1。
S2：带有2：如果达到最后一个数字（4），则可以形成1个潜在的三元组。将2添加到散列表。
S3：带有4：如果达到最后一个数字（8），可能会形成1个潜在的三元组。在散列表中添加4。同时，我们有1个三元组，因为4/2和4/2/2存在于散列表中。
但是我们怎么知道只有1，因为要到达一个三元组的第4个，你必须经过第2个，而我们只有1，第2个在第4个之前。
所以总数是1。简单。

如果输入为1 2 2 2 4会怎样？

我们有潜力：1：0; 2：1第一;4：3数字2 =〉3个三胞胎
将1添加到输入，我们得到：1 1 2 2 2 4和r=2
对于第一个2，我们有2个潜在的三重态，因为在它之前有2数字1。
对于第二个2，我们有两个
对于第三个2，我们有三个
因此，总数为2（1号）x 3（2号）= 6个潜在三重态
当索引达到数字4时，类似于上面的步骤3，我们有总的三元组是6。
这是我们通过数组迭代的2个散列表的演示：
| 输入|潜力|计数|
| - ------|- ------|- ------|
| 一一二二二四|{1：0、2：6、4：3}|{1：2、2：3、4：1}|
| 1 1 2 2 2 4 8 16|{1：0、2：6、4：3、8：1、16：1}|{1：2、2：3、4：1、8：1、16：1 }|
作为上表中的第二个输入，我们可以说：
对于三重态数（1，2，4），我们有6个三重态（在数2处的势）
对于三重态数（2，4，8），我们有3个三重态（在数4处的势）
对于三重态数（4，8，16），我们有1个三重态（在数8处的势）
所以总共是10个三胞胎。
这是我的javascript解决方案

function countTriplets(arr, r) {
const numberAtThisPointOf = {};
const potentialTripletOf = {};
let total = 0;

for (let i = 0; i < arr.length; i++) {
  const key = arr[i];
  if (numberAtThisPointOf[key] === undefined) {
    potentialTripletOf[key] = 0;
    numberAtThisPointOf[key] = 0;
  }
  
  // if key is final part of a triplet, mean the other 2 smaller numbers exist, the `key % r === 0` & `(key/r) % r === 0` to avoid decimal number in javascript
  if (key % r === 0 && numberAtThisPointOf[key/r] !== undefined & numberAtThisPointOf[key/r/r] !== undefined && (key/r) % r === 0) {
    total += potentialTripletOf[key/r];
  }
  
  // update potential case of current key
  if (numberAtThisPointOf[key/r] !== undefined && key % r === 0) {
    potentialTripletOf[key] += numberAtThisPointOf[key/r];
  }
  
  numberAtThisPointOf[key]++;
  
  }
  return total; 
}

可以是下面这样的想法。
几何级数的形式为：啊，啊，啊，...
现在考虑arr中的元素是否为：
1.元素== ARR或三元组的第三项意味着我们已经完成三元组，因此更新计数。
1.元素== AR或三元组的第二项，因此GP中的下一个元素将是（元素乘以R）ARR，并将在ARR或r3字典中更新。
1.元素== A或第一项，因此GP中的下一个元素将是（元素乘以R）AR，因此将在AR或r2字典中更新。