来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-triangle-number
题目描述：
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
题目分析：
- 要组成三角形，则需要满足两边之和大于第三边，也就是作为三角形3边的三个元素，任意两个之和，必须大于第三个元素 。
思路一:
假设数组nums[a,b,c...]正序有序,则a <= b <= c，a + c > b, b + c > a肯定成立，所以我们只需要再保证a + b > c，a,b,c就可以组成三角形。因此我们首先对数组进行正序排序，然后暴力遍历所有的个数，只要a + b > c，result加一(该方法比较耗时，时间复杂度击败5%)
611. 有效三角形的个数.png
代码实现
class Solution {
public int result = 0;
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int len = nums.length - 1;
for (int i = 0; i <= len - 2; i++) {
for (int j = i + 1; j <= len - 1; j++) {
sum(nums, i, j, len);
}
}
return result;
}
public void sum(int[] nums, int i, int j, int len) {
int q = j + 1;
while (q <= len && nums[i] + nums[j] > nums[q]) {
q++;
result++;
}
}
}
思路二：
因为排序之后数组nums是有序的，所以在寻找nums[i] + nums[j] > nums[q]的时候，可以利用二分法，直接找到边界，例如：snums[3, 5, 5, 7, 7], nums[0] + nums[1] > nums[2],nums[0] + nums[1] > nums[3],nums[0] + nums[1] > nums[4],这个过程 我们可以直接利用二分法找到边界索引4.则4左边的都是满足nums[i] + nums[j] > nums[q],右边则是不满足的。
代码实现：
class Solution {
public int result = 0;
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int len = nums.length - 1;
for (int i = 0; i <= len - 2; i++) {
for (int j = i + 1; j <= len - 1; j++) {
sum(nums, i, j, len);
}
}
return result;
}
public void sum(int[] nums, int i, int j, int len) {
int q = j + 1;
int left = q, right = len, index = j;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] < nums[i] + nums[j]) {
index = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
result += index - j;
}
}
思路三
从上面的图可以看到每次重新初始化j = j + 1时，也会将q重新初始化为 q = j + 1,但是对于正序nums来说，如果nums[i] + nums[j] > nums[q]，那么nums[i] + nums[j+1] > nums[q]也是成立的，因此初始化j = j + 1时，可以不用将q也初始化。
代码实现：
class Solution {
public int result = 0;
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int len = nums.length - 1;
for (int i = 0; i <= len - 2; i++) {
int q = i + 1;
for (int j = i + 1; j <= len - 1; j++) {
while ((q + 1) <= len && nums[i] + nums[j] > nums[q + 1]) {
q++;
}
q = q > j ? q : j; // 防止一个满足条件的都没有
result += q - j;
}
}
return result;
}
}
