- 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].
题意:
给定数组, 可由数组中的数字组成多少个 valid 三角形
解本题的背景知识: [Math fact] The sum of two sides of a triangle must be greater than the third one
- Solution1: Two Pointers (similar as 3 Sum problem)
- 1. sort array
- 2. lock pointer k at the trail (must be largest side)
- [2, 2, 3, 4]
- ^k
- 3. set pointer left at 0, right at k-1
- [2, 2, 3, 4]
- ^k
- ^left ^right
- Lock pointer k and pointer right
- check if nums[left] + nums[right]> nums[k]
- (1)YES. Then we can say (nums[left + 1] / nums[left + 2]....) + nums[right]> nums[k]
- So combination count: right - left
- Then lock pointer k and pointer right -1 to get next combination count
- (2) No. Then left ++
- code
- /*
- Time: O(n^2)
- Space: O(1)
- */
- class Solution {
- public int triangleNumber(int[] nums) {
- if(nums == null || nums.length == 0) return 0;
- Arrays.sort(nums);
- int result = 0;
- for (int k = nums.length - 1; k> 0 ; k--) {
- int left = 0;
- int right = k - 1 ;
- while (left <right) {
- if (nums[left] + nums[right]> nums[k]) {
- result += (right - left);
- right--;
- }
- else {
- left++;
- }
- }
- }
- return result;
- }
- }
[leetcode]611. Valid Triangle Number 有效三角数
来源: http://www.bubuko.com/infodetail-3046034.html