有效三角形的个数

给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]

输出: 3

解释:

有效的组合是:

2,3,4 (使用第一个 2)

2,3,4 (使用第二个 2)

2,2,3

注意:

数组长度不超过1000。
数组里整数的范围为 [0, 1000]。

思路

我们都知道，要想构成三角形，只需三角形中两条最短边之和大于最长边即可。

基于这样的原理，我们可以先将数组从小到大进行排序。将数组排序后，我们可以这样想，固定某一个数，然后用左右两个指针分别指向某个数，当左右指针指向的数字之和大于我们固定的数时，说明此种情况成立。然后将右指针向左移动一位继续判断直到不满足为止，将左指针向右移动一位继续判断；直到左指针跟右指针重合。

根据这个思路，我们将数组从大到小遍历，将当前遍历的数nums[i]进行固定，让左指针指向第0个数nums[0]，右指针指向这个数的左边一个数nums[i-1]。当nums[left]+nums[right]>nums[i]时，把右指针right固定，可以想到：当左指针left往右遍历时，左指针与右指针之间的和肯定也满足要求；因此有count+=(right-left)。

将右指针right往左移一位，继续进行判断，如果成立，则right继续重复前面操作；如果不成立，说明两个数之和太小了，此时将左指针left往右移一位，继续进行判断，直到left与right指针重合，这样就把nums[i]所有的情况都考虑了，最后数组遍历完结果就出来了。

 import java.util.Arrays;

 class Solution {

     public int triangleNumber(int[] nums) {

         int count=0,size=nums.length;

         Arrays.sort(nums);

         for(int i=size-1;i>=2;i--){

             int left=0,right=i-1;

             while(left<right){

                 if(nums[left]+nums[right]>nums[i]){

                     count+=(right-left);

                     right--;

                 }else{

                     left++;

                 }

             }

         }

         return count;

     }

 }

巴特西

Leetcode 611.有效三角形的个数

有效三角形的个数

思路

最新文章

热门文章