611. Valid Triangle Number

问题：

求给定数组中，每三个值作为三角形三边，可构成三角形的集合个数。

Example 1:
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].

　　

解法：

先sort整个数组

i 指向最大边，固定不变

j 指向第二大边，k 指向最小边。调整 j 和 k

初始化，i=数组最大值，依次-1，j=i-1，k=0

若nums[k]+nums[j]<=nums[i]，两边之和小于等于第三边，不满足三角形。那么需要扩大 k + j 的和，j已经（除了不能动的i）最大，那么调整 k，k++。

反之，满足三角形，那么大于当前 k 和 j 的和的所有(当k=k~j-1的所有值+j)都满足，res+=(j-k)。

接着稍微使得满足条件的 j-- 减小，看看当前 k 是否还能满足。不满足的话增大 k++，同上循环。

代码参考：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        if(nums.size()<3) return 0;
        sort(nums.begin(),nums.end());
        int i, j, k;
        int res=0;
        for(i=nums.size()-1; i>1; i--){
            j=i-1;
            k=0;
            while(k<j){
               if(nums[k]+nums[j]<=nums[i]){//not good
                   k++;
                }else{
                   res+=(j-k);
                   j--;
                }
            }
        }
        return res;
    }
};