这两个题几乎一样，只是说611. Valid Triangle Number满足大于条件，259. 3Sum Smaller满足小于条件，两者都是先排序，然后用双指针的方式。
611. Valid Triangle Number
判断这个数组能组成三角形的个数，利用两边之和大于第三边
https://www.cnblogs.com/grandyang/p/7053730.html
暴力方法是找所有3个数的组合，看满足条件的，时间复杂度是O(n3)。
此方法时间复杂度为O(n2)。先排序，然后left是第0个，right是i-1，进行比较。如果left+right大于了当前遍历的值，那么left往上移动到right中经过的值都能满足，因为left相对于那些数反而是最小的，既然小的都能满足，大的也能满足。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
if(nums.size() <= )
return ;
int res = ;
sort(nums.begin(),nums.end());
for(int i = ;i < nums.size();i++){
int left = ,right = i-;
while(left < right){
if(nums[left] + nums[right] > nums[i]){
res += right - left;
right--;
}
else
left++;
}
}
return res;
}
};
259. 3Sum Smaller
http://www.cnblogs.com/grandyang/p/5235086.html
这个题是寻找3个数之和小于目标值，暴力的方法也是将所有3个数的可能性遍历寻找满足条件的个数。
这个题的O(n2)的方法与611. Valid Triangle Number几乎一样，只是说因为这个题寻找的是小于目标值，所以满足条件后，应该是right往下走，因为right往下的才更小才能满足条件。
注意：这里选择是left是0，right是i-1，也就是说我每次作为基本递归的是最大的那个数
class Solution {
public:
/**
* @param nums: an array of n integers
* @param target: a target
* @return: the number of index triplets satisfy the condition nums[i] + nums[j] + nums[k] < target
*/
int threeSumSmaller(vector<int> &nums, int target) {
// Write your code here
if(nums.size() <= )
return ;
sort(nums.begin(),nums.end());
int res = ;
for(int i = ;i < nums.size();i++){
int left = ,right = i-;
while(left < right){
if(nums[left] + nums[right] + nums[i] < target){
res += right - left;
left++;
}
else
right--;
}
}
return res;
}
};