给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？
在线评测地址：领扣题库官网
样例 1:
输入: [3, 4, 6, 7]
输出: 3
解释:
可以组成的是 (3, 4, 6),
(3, 6, 7),
(4, 6, 7)
样例 2:
输入: [4, 4, 4, 4]
输出: 4
解释:
任何三个数都可以构成三角形
所以答案为 C(3, 4) = 4题目理解
- 我们先考虑“三条边能构成三角形”的充分必要条件。我们首先想到的是“三角形的任意两边之和大于第三边，三角形的任意两边之差小于第三边”。如果从这个角度理解，代码编写比较麻烦，因为“任意”二字就要求我们去检验各种组合。
- 如果我们仔细分析一下这个条件，就不难证明它等效于“较短的两边之和大于最长边”。对于升序排列的三个数[a, b, c]，我们只需判断a + b > c是否成立，就知道它们是否能构成三角形。
解题思路
- 最直观的方法是暴力法，三重循环枚举，时间复杂度为O(n^3)。
- 如果先将数组排好序，二重循环固定较短两边a和b，然后再利用二分查找找到最大的满足a + b > c的c，这样可以将时间复杂度优化至O(n^2logn)
- 这里我们采用双指针方法，可以继续降低时间复杂度。首先固定最大边的位置 i，然后在 [0, i-1]之间利用双指针找到满足条件的三边。时间复杂度为O(n^2)。
算法流程
- 首先对数组进行升序排列。
-
从右向左遍历最大边，固定最大边的位置i
- 建立双指针left和right，初始分别指向0和i-1
- 如果S[left] + S[right] > S[i]，说明三者可以构成三角形。与此同时，最小边的索引为left+1, left+2,...,right-1时，都能与S[right]和S[i]构成三角形。所以满足条件的三角形找到了right-left个。然后right指针左移进入下一轮。
- 如果S[left] + S[right] <= S[i]，说明不能构成三角形。left指针右移进入下一轮。
复杂度分析
- 时间复杂度为O(n^2)。外层遍历最大边是n，内层循环移动双指针是n，所以总复杂度为O(n^2)。
- 空间复杂度为O(1)，只需占用常量空间。
public class Solution {
/**
* @param S: A list of integers
* @return: An integer
*/
public int triangleCount(int[] S) {
int res = 0;
int left = 0, right = S.length - 1;
// 先对S进行排序
Arrays.sort(S);
// 最大边从右向左遍历
for (int i = 0; i < S.length; i++) {
// 建立双指针
left = 0;
right = i - 1;
while (left < right) {
// 可以构成三角形
if (S[left] + S[right] > S[i]) {
res += (right - left);
right --;
}
// 不能构成三角形
else {
left ++;
}
}
}
return res;
}
}更多题解参考：九章官网solution
