如何有效地在数组中找到两个元素之和等于第三个元素的三元组？

Question

问题陈述：

Dan 将 $f(x)$ 定义为数字 $x$ 的除数个数。例如，$f(6) = 4$（6 的约数为 1、2、3 和 6）。

我们考虑一个三元组 $(i, j, k)$ （其中 $1 \leq i < j < k \leq n$) as a "perfect triplet" if it satisfies: $f(a_i) - f(a_j) = f(a_k)$.

给定一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$，Dan 想知道存在多少个不同的完美三元组。

如果两个三元组至少有一个索引不同，则认为它们不同。例如，$(1, 2, 3)$ 和 $(1, 2, 4)$ 是两个不同的三元组。

输入说明：

• 第一行包含一个整数 $n$ $(3 \leq n \leq 10^5)$ 表示数组的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(1 \leq a_i \leq 10^6)$ 表示数组的元素。

输出说明：

• 输出一个整数，表示完美三元组的数量。

---

我正在解决一个问题，我需要预处理一个数组以确定每个元素的除数数量，从而得到一个数组 $f$。目标是在 $f$ 数组中找到三个元素，使得两个元素之和等于第三个元素，同时确保索引满足 $1 \leq i < j < k \leq n$.

我的思考过程：

1. 我最初考虑将除数计数预处理到 $f$ 数组中，这很简单。接下来的挑战就变成了找到三元组 $(f[i], f[j], f[k])$ 使得 $f[i] + f[j] = f[k]$，且索引满足 $i < j < k$.

2. 我最初的方法涉及检查每个可能的三元组，这自然会导致 $O(n^3)$ 解决方案，因此我探索了优化。

3. 我尝试通过首先对 $f$ 数组进行排序，然后使用双指针技术与二分搜索相结合，将复杂度降低到 $O(n^2)$。然而，我很快意识到，虽然这通常适用于查找三元组，但它并没有考虑严格的索引约束，其中 $i < j < k$ in the original unsorted array.

4. 我现在正试图进一步优化这个解决方案。我所有的方法似乎仍然涉及嵌套循环或某种变体，将复杂性保持在 $O(n^2)$。

有没有一种更有效的方法来解决这个问题，最好是在尊重索引约束的情况下将时间复杂度降低到 $O(n^2)$ 以下？

Answer 1

• 对数组进行排序。
• 使用左右两个指针（

  lo

  、

  hi

  ）。
• 循环数组一次：
• 当

  lo

  小于

  hi

  时：(a)计算三个数字的总和
• 如果总和为负数，则移动左指针。
• 如果总和为正，则向右移动指针。
• 如果总和等于零，我们就有一个三元组。

def find_triplets(nums):
    triplets = []
    nums.sort()

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        lo, hi = i + 1, len(nums) - 1

        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]

            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])

                while lo < hi and nums[lo] == nums[lo + 1]:
                    lo += 1
                while lo < hi and nums[hi] == nums[hi - 1]:
                    hi -= 1

                lo += 1
                hi -= 1

    return triplets


print(find_triplets([-1, 0, 1, 2, -1, 10, 11, 12, -4, -12, 3, 3, 5, 6, 7, 8, 9, 7, -4, -6, 13]))

打印：

[[-12,-1,13],[-12,0,12],[-12,1,11],[-12,2,10],[-12,3,9], [-12,5,7],[-6,-4,10],[-6,-1,7],[-6,0,6],[-6,1,5],[-6 , 3, 3], [-4, -4, 8], [-4, -1, 5], [-4, 1, 3], [-1, -1, 2], [-1, 0, 1]]