从数组中查找三角形

给出由 N 个整数组成的零索引数组 A。三元组 (P, Q, R) 是三角形，如果且

A[P] + A[Q] > A[R], 
A[Q] + A[R] > A[P], 
A[R] + A[P] > A[Q]. 

例如，考虑数组 A，使得

A[0] = 10    A[1] = 2    A[2] =  5
A[3] =  1    A[4] = 8    A[5] = 20

三元组 (0, 2, 4) 是三角形。 写一个函数

int triangle(const vector<int> &A);

给定一个由 N 个整数组成的零索引数组 A，如果该数组存在三角形三元组，则返回 1，否则返回 0。

假使，假设：

N是[0..100,000]范围内的整数； 数组 A 的每个元素都是 [-2,147,483,648..2,147,483,647] 范围内的整数。 例如，给定数组 A，使得

A[0] = 10 A[1] = 2 A[2] = 5 A[3] = 1 A[4] = 8 A[5] = 20 该函数应返回 1，如上所述。给定数组 A 使得 A[0] = 10 A[1] = 50 A[2] = 5 A[3] = 1 该函数应返回 0。 预期最坏情况时间复杂度：
预期最坏情况空间复杂度：O(1)

第一次索赔

首先，没有必要考虑非正数。如果至少有一个数字为负数或零，则不可能实现三角不等式。这是显而易见的，但这里有证据：

假设 A、B、C 服从三角不等式，而 C

• A + C > B。因此 A > B。
• B + C > A。因此 B > A。

（矛盾）。

第二项索赔

假设A、B、C服从三角不等式，而C是A、B、C中最大的。那么对于 A、B 和 C 之间的每个 A2 和 B2 - 它们也将遵守三角不等式。

换句话说：

• A、B、C 服从三角不等式。
• C >= A
• C >= B
• C >= A2 >= A
• C >= B2 >= B
• 那么A2,B2,C也服从三角不等式。

证明很简单，足以明确地写出不等式。

其结果是，如果 C 是您要查找三角不等式的最大数 -您应该只检查集合中不超过 C 的两个最大数字，并检查是否 A + B > C。

第三项主张

如果 0 = A*2。

证明也很简单：A + B = A*2

算法

1. 选择 2 个最大的数字 B 和 C (B
2. Pick the largest number A not exceeding B, such that
   • A
   • 确保它与 B,C 不是同一元素
   • 仅考虑正整数。
   • 如果无法选择这样的数字 - 完成。 （没有三角形）。
3. 检查A、B、C是否满足三角不等式。测试是否 A + B > C（如果是则完成）。
4. 丢弃最大的数 C。代入 C = B，则 B = A。
5. 转到步骤 2。

第四项主张

上述算法在最大整数大小上是对数的。换句话说，它与数据类型位数呈线性关系。最坏情况的复杂度是独立的关于输入长度。因此 - 输入长度为 O(1)。

Proof:

在每次迭代（未找到解决方案）时，我们都有 A 新C。这意味着每两次迭代后，最大数字至少会小 2 倍。

显然，这给了我们迭代次数的上限。给定我们的整数受到 31 位的限制（我们忽略负数），而最小有趣的最大 C 是 1，这给我们的结果就是 2 * (31 - 1) =60次迭代.