fms 视频网站建设/seo诊断站长

这两个题几乎一样，只是说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() <= 2)return 0;int res = 0;sort(nums.begin(),nums.end());for(int i = 2;i < nums.size();i++){int left = 0,right = i-1;while(left < right){if(nums[left] + nums[right] > nums[i]){res += right - left;right--;}elseleft++;}}return res;}
};

 

 

259. 3Sum Smaller

http://www.cnblogs.com/grandyang/p/5235086.html

这个题是寻找3个数之和小于目标值，暴力的方法也是将所有3个数的可能性遍历寻找满足条件的个数。

这个题的O(n2)的方法与611. Valid Triangle Number几乎一样，只是说因为这个题寻找的是小于目标值，所以满足条件后，应该是right往下走，因为right往下的才更小才能满足条件。

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() <= 2)return 0;sort(nums.begin(),nums.end());int res = 0;for(int i = 2;i < nums.size();i++){int left = 0,right = i-1;while(left < right){if(nums[left] + nums[right] + nums[i] < target){res += right - left;left++;}elseright--;}}return res;}
};