java - 查找数组中的对数，其中 A[i] * A[j] > A[i] + A[j]

Question

例如如果数组 A 是

A[0] = 0.1
A[1] = 0.6
A[2] = 1.2
A[3] = 1.7
A[4] = 3.5

然后对于 (3,4) 对，我们有 A[3]*A[4] > A[3]+A[4]

我想找出数组中此类对的数量。

还有 A[i] = A1[i] + A2[i]/1,000,000

其中 A1 和 A2 是给定的输入，A1 和 A2 已排序。

用 O(n^2) 算法回答是微不足道的。有人告诉我有 O(n) 解决方案，无需使用额外空间。我正在寻找那个。

Answer 1

x * y > x + y

除以 x*y(对于正值)

1/x + 1/y < 1

让我们第一个光标(R)指向右边的元素(最小 1/a[i] 值)，第二个光标(L)指向左边的元素。
将L向右移动，直到倒数和为1。
将 (R-L) 添加到结果。
向左走 R 步。
重复移动L，直到R和L相遇

两个游标最多移动 N 步，所以算法需要 O(N)