This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging

611. Number of valid triangles

Title Description

Given an integer array nums, return 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: nums = [2,2,3,4] Output: 3 Explanation: Valid digit are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3Copy the code

Example 2:

Input: nums = [4,2,3,4]
Output: 4
Copy the code

Constraints:

1 <= nums.length <= 1000 0 <= nums[i] <= 1000

Topic describes

Given an array of non-negative integers, your task is to count the number of triples that make up the three sides of a triangle.

Example 1:

Input: [2,2,3,4] Output: 3 Explanation: The valid combination is: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3Copy the code

Note:

The array length does not exceed 1000. The range of integers in the array is 0, 1000.

1

Sort + double pointer

  • We use a loop to enumerate I. When I is fixed, we use double Pointers to maintain both j and k, both of which start at I;

  • We move J to the right by one position each time, that is, J ← J +1, and try to move K to the right constantly, so that K is the maximum subscript of nums[k]<nums[I]+nums[j]. We add Max (k−j,0) to the answer.

code

class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(),nums.end()); int ans=0; for(int i=2; i<nums.size(); ++i){ int k=0; for(int j=i-1; k<j; --j){ while(k < j&&nums[j]+nums[k]<=nums[i])++k; ans+=j-k; } } return ans; }};Copy the code

2

Sort + binary search

  1. First sort, then binary search
  2. If the first two numbers are a and b, and a<=b, then the range of the third number is [b,a+b-1].
  3. Using dichotomy, look for nums in the remaining range: greater than or equal to the minimum value of lower, and less than or equal to the maximum value of upper.
  4. Because of the dichotomy, if you look to the right for the maximum value less than or equal to upper, you may find the first value greater than upper, and then compare it to see if you take a step back.

code

class Solution { public int triangleNumber(int[] nums) { int n = nums.length; if(n<3) return 0; Arrays.sort(nums); int ans = 0; for(int i = 0; i<n-2; i++){ for(int j = i+1; j<n-1; j++){ int sum2 = nums[i]+nums[j]; if(nums[j+1]>=sum2)continue; int lower = nums[j+1]; int upper = sum2-1; // Find the lowest value between :j+1 and n-1 greater than or equal to lower, return the coordinates. int minId = searchMin(nums, j+1, n-1, lower); // Find the maximum value between :j+1 and n-1 that is less than or equal to upper. int maxId = searchMax(nums, j+1, n-1, upper); // System.out.println("i="+i+",j="+j+", lower="+lower+", upper="+upper+",minId="+minId+", maxId="+maxId); ans+=1 + maxId - minId; } } return ans; } int searchMin(int[] nums, int left, int right, int target){ while(left<right){ int m = (left+right)>>>1; if(nums[m]>=target) right=m; else left=m+1; } return left; } int searchMax(int[] nums, int left, int right, int target){ while(left<right){ int m = (left+right)>>>1; if(nums[m]<=target) left=m+1; else right=m; } if(nums[left]>target)return left-1; return left; }}Copy the code