题目地址：

https://www.lintcode.com/problem/valid-triangle-number/description

给定一个包含非负整数的数组$A$，问从其能挑出多少三元组可以作为三角形的三个边长。

如果$l_A<3$直接返回$0$。接着将$A$由小到大排序，然后从$A[2]$开始向后遍历，每次遍历到$A[i]$的时候相当于求一下$A[0:i-1]$中和大于$A[i]$的数对个数，这可以用对撞双指针算法解决。开两个指针$l$和$r$分别从$0$和$i-1$出发，如果$A[l]+A[r]>A[i]$，那么可以知道$A[l:r-1]$的所有数字与$A[r]$的和都大于$A[i]$，累加个数$r-l$并左移$r$；否则右移$l$。代码如下：

import java.util.Arrays; public class Solution { /** * @param nums: the given array * @return: the number of triplets chosen from the array that can make triangles */ public int triangleNumber(int[] nums) { // Write your code here if (nums.length < 3) { return 0; } int res = 0; Arrays.sort(nums); for (int i = 2; i < nums.length; i++) { int l = 0, r = i - 1; while (l < r) { int sum = nums[l] + nums[r]; if (sum > nums[i]) { res += r - l; r--; } else { l++; } } } return res; } }

时间复杂度$O(n^2)$，空间$O(1)$。