611. Valid Triangle Number
https://leetcode.com/problems/valid-triangle-number/
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:
- The length of the given array won't exceed 1000.
- The integers in the given array are in the range of [0, 1000].
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public int triangleNumber(int[] nums) { | |
| Arrays.sort(nums); | |
| int ans = 0; | |
| for (int i = nums.length - 1; i > 1; i--) { | |
| int l = 0, r = i - 1; | |
| while (l < r) { | |
| if (nums[l] + nums[r] > nums[i]) { | |
| // If l + r > then sum of all numbers between l, r > i | |
| ans += r - l; | |
| r--; | |
| } else { | |
| // sum is smaller, try the next higher number | |
| l++; | |
| } | |
| } | |
| } | |
| return ans; | |
| } | |
| } |
