The number of effective triangles

Topic link
Title Description ：
Given an array of non negative integers nums , Returns the number of triples that can form three sides of a triangle
Input ：
nums = [2,2,3,4]
Output ：
3

---

Ideas 1：

1. Sort + Two points ： Prioritize , Ascending order guarantees the first two conditions for forming a triangle a+c>b b+c>a
2. Double cycle （ Satisfy a<b）
3. Dichotomy from b The next start of , Find the most satisfying condition, that is a+b>c Of c, From this position to b Next in position (k-j) It is the trilateral case that meets the conditions
4. Continue to cycle

Ideas 2：

1. Double pointer + Two points ( Reverse scanning )： Prioritize , And then traverse in reverse order nums Array （ First determine the maximum edge a, As long as the remaining two sides meet b + c > a, You must be satisfied a + c > b and a + b > c）
2. nums[i] For certain a edge ,l=0（b edge , Left pointer ）r=i-1（c edge , Right pointer ）
3. Combine dichotomy while(l<r)
   As long as meet b + c > a Just r–, c The edge is fixed to nums[r], meanwhile b The edge can be seen from l Fetch r-1 common r-l In this case ,cnt+=l-r;
   otherwise l++
4. Be careful ： Why not use forward scanning here ？
   answer ： When scanning forward , If the sum of the 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 . Reverse scanning can only say that the left pointer is to the right

The code is as follows Sort + Two points ：

class Solution {
      
public:
    int triangleNumber(vector<int>& nums) {
     
        // Sort + Two points 
        sort(nums.begin(),nums.end());//less  Ascending order guarantees the first two conditions for forming a triangle a+c>b b+c>a
        // All that remains is to meet a+b>c
        int cnt=0;// Count 
        for(int i=0;i<nums.size();i++)// Double cycle （ Satisfy a<b）
        {
     
            int a=nums[i];
            for(int j=i+1;j<nums.size();j++)
            {
     
                int b=nums[j];  
                int l=j+1;// from j+1 Start 
                int r=nums.size()-1;// To the end of the array 
                int k=j;// Final satisfaction c The number of may be 0 individual 
                while(l<=r)// Split template 
                {
     
                    int mid=(l+r)/2;
                    if(a+b>nums[mid])
                    {
     
                        k=mid;
                        l=mid+1;
                    }
                    else
                        r=mid-1;
                }
                cnt+=(k-j);// The maximum value that satisfies the condition j+1~max It's all possible c Value obtained  
            }
        }
        return cnt;
    } 
};

The code is as follows Double pointer + Two points ：

class Solution {
      
public:
    int triangleNumber(vector<int>& nums) {
     
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int cnt=0;
        for(int i=n-1;i>=2;i--)
        {
     
            int l=0;
            int r=i-1;
            while(l<r)
            {
     
                if(nums[l]+nums[r]>nums[i])
                {
     
                    cnt+=r-l;
                    r--;
                }
                else
                    l++;
            }
        }
        return cnt;
    } 
};