力扣-有效三角形的个数

1.题目描述

2.题目链接

611. 有效三角形的个数 - 力扣（LeetCode） 

3.题目代码

class Solution {public int triangleNumber(int[] nums) {//先排序Arrays.sort(nums);//若a<=b<=c,三角形条件可以优化为:a+b>cint temp=nums.length-1,sum=0;while(temp>1){int left=0,right=temp-1;while(left<right){if(nums[left]+nums[right]>nums[temp]){sum+=right-left;right--;}else {left++;}}temp--;}return sum;}
}

4.解题思路

1.有效三角形的条件

首先，我们要知道三角形形成的条件是：任意两边和大于第三边，也就是：

对于三条边长 a、b、c（假设 a≤b≤c），构成三角形需满足以下三个不等式同时成立：

1. a+b>c
2. a+c>b
3. b+c>a

但是，我们可以先对数组进行排序，保证a<=b<=c，此时构成三角形的条件只需要满足：a+b>=c，因为c本身就大于a和b，所以c加上a或者b一定大于另一个数，2和3也就天然成立。

2.双指针和定数

这道题我们可以使用双指针和定数来解决。

首先，定义一个定数temp，让temp指向数组的最后一个元素，也就是temp=nums【nums.length-1】。

再定义两个指针left和right，分别让它们指向剩下数组的最左边和最右边，也就是left=0，right=temp=nums.length。

3.结合单调性移动双指针

1）.nums【left】+nums【right】>nums【temp】，这时构成三角形，而且因为left和right分别是剩下数组的最左边和最右边，所以nums【left】和nums【right】也就是剩下数组的最小值和最大值。

所以left到right之间的数，加上nums【right】都大于nums【left】>nums【right】>nums【temp】。也就是说，从left下标到right-1下标的数字，和right下标的数都可以构成三角形。

所以我们直接让结果sum+=right-left。

然后移动指针，让right指针左移，也就是right--。

2）.nums【left】+nums【right】<=nums【temp】，因为nums【right】已经是剩下数组的最大值了，想要让不等式左边值变大满足三角形条件，就是需要nums【left】变大，也就是右移left指针，让left++。

直到left和right相遇，循环结束。此时我们改变temp定值，使temp左移一位。

5.代码细节

1）可以使用Arrays.sort(nums);来先对数组进行排序，这在很多题目里面非常重要。

Arrays.sort(nums);

2）因为left和right的定义是剩余数组的边界，所以left和right应该是随着temp的改变不断改变的，所以left和right应该定义在temp循环内部。

 while(temp>1){int left=0,right=temp-1;while(left<right){if(nums[left]+nums[right]>nums[temp]){sum+=right-left;right--;}else {left++;}}temp--;}

3）temp的while循环结束条件是temp>1,因为此时temp在数组第二个元素，他的左边只有1个元素，不可能构成三角形。