Rule method: number of effective triangles

Ruler method ： The number of effective triangles

problem ：

Ideas ：

   This problem needs to be solved by using the rule taking method of three elements , The rule method of three elements is to enumerate one , Then use the double pointer to scan the rest of the interval , The other two elements are the left end point and the right end point of the interval , Move one of the two elements according to the different conditions in the question
   Let's sort the array in the question first , The three sides grow from small to large a、b、c, If and only if a + b > c These three sides can form a triangle . This problem can only enumerate the largest edges for reverse scanning , If you are enumerating the shortest edge forward scan , If the sum of two sides is less than the third side , Then there are two situations , One is to move the left pointer to the right , One is to move the right pointer to the left , The situation of movement is uncertain . When enumerating the maximum edge reverse scanning , If the sum of the two sides is less than the third side , It can only be left pointer to right , The movement is certain , If the sum of two sides is greater than or equal to the third side , It can only be the right pointer to the left .
   So we enumerate the rightmost maximum values of the array , Subscript k, In the remaining interval , The right end of the interval is the second largest value , Subscript to be j = k - 1, Minimum subscript i = 0 Start , if nums[i] + nums[j] > nums[k], that i From the present i Start , Until j - 1, Can meet this condition , So we found j - i Valid triangles , At the same time, turn the right pointer to the left ,j - -, Look for other conditions . if nums[i] + nums[j] <= nums[k], Turn the left pointer to the right ,i ++. stay i >= j when , We will traverse all the cases in the interval .

Code ：

    public int triangleNumber(int[] nums) {
    
        // write code here
        Arrays.sort(nums);
        int ans = 0;
        int i, j, k;
        for (k = nums.length - 1; k >= 2; k--) {
    
            j = k - 1;
            i = 0;
            while (i < j) {
    
                if (nums[i] + nums[j] > nums[k]) {
    
                    ans += (j - i);
                    j--;
                } else {
    
                    i++;   
                }
            }
        }
        return ans;
    }