【优选算法】有效三角形的个数（双指针算法）

class Solution {
public:
	int triangleNumber(vector<int>& nums) {
		// 1. 排序
		sort(nums.begin(), nums.end());
		int n = nums.size(), ret = 0;
		// 2. 从⼩到⼤枚举所有的三元组
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				for (int k = j + 1; k < n; k++) {
					// 当最⼩的两个边之和⼤于第三边的时候，统计答案
					if (nums[i] + nums[j] > nums[k])
						ret++;
				}
			}
		}
		return ret;
	}
};

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        //1.先对数组进行排序
        sort(nums.begin(),nums.end());

        //2.利用双指针解决问题
        int ret = 0,n = nums.size();
        for(int i = n-1;i>=2;i--)//固定最大的那个数
        {
            int left = 0,right = i-1;
            while(left < right)
            {
                if((nums[left]+nums[right])>nums[i])
                {
                    ret += right-left;
                    right--;
                }
                else
                    left++;
            }
        }
        return ret;
    }
};