C#版 - Leetcode611.有效三角形的个数 - 题解

输入: [2,2,3,4]
输出: 3

解释:
有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

sort(nums)

for c = n-1 to 2 
  a, b = 0, c-1
  while a<b: 
    if nums[a] + nums[b] > nums[c]: 
        count += (a-b+1)-1
        b--
    else 
        a++

public class Solution
{
    public int TriangleNumber(int[] nums)  
    {
        var n = nums.Length;
        if (n < 3)
            return 0;

        Array.Sort(nums);
        // Array.Sort(array, (x, y) => -x.CompareTo(y));
        var groupCount = 0;

        for (int c = n - 1; c >= 2; c--)
        {
            int b = c - 1;
            int a = 0;
            while (a != b)
            {
                if (nums[a] + nums[b] > nums[c])
                {
                    groupCount += b - a; // 贪心法，只要此时满足不等式，则仅有a在该区间内移动(b，c不变)时，显然也满足不等式
                    b--;
                }
                else
                    a++;
            }
        }

        return groupCount;
    }
}