网络服务类型有哪些_宁波荣胜网络科技有限公司_成都网站搜索排名优化公司_百度热线人工服务电话

1.题目

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

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

提示:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

2.算法原理

利用单调性，使用双指针算法来解决。

• 先固定最大的数
• 最最大的数的左区间，使用双指针算法，快速统计处符合要求的三元组的个数

class Solution {
public:int triangleNumber(vector<int>& nums) {//优化排序sort(nums.begin(),nums.end());//利用双指针int n=nums.size();int ret = 0;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--;elseleft++;}}return ret;  }
};