Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:
Input: [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3
Note:
找出满足组成三角形的三条边的个数
思路：组成三角形条件是两条较短的边的和大于第三条边
1 public int triangleNumber(int[] nums) { 2 Arrays.sort(nums); 3 int count = 0; 4 for (int i = nums.length - 1; i >= 2; i--) { 5 int left = 0, right = i - 1; 6 while (left < right) { 7 if (nums[left] + nums[right] > nums[i]) { //最短的两条边之和大于最长的边nums[i] 8 count += right - left; //[left.right-1) 区间里面的数+right都满足条件 9 right--; 10 } else { 11 left++; 12 } 13 } 14 } 15 return count; 16 }
原文：http://www.cnblogs.com/wzj4858/p/7678495.html