展馆网站建设方案,温州建设,株洲网站设计外包首选,网站设计制作太原给定一个包含非负整数的数组 nums #xff0c;返回其中可以组成三角形三条边的三元组个数。
示例 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
代码如下#xff1a;…给定一个包含非负整数的数组 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
代码如下
//排序双指针
class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(),nums.end());//先将数组进行排序int nnums.size();int count0;//记录有效三角形的个数for(int in-1;i2;i--){int left0;int righti-1;while(leftright){if(nums[left]nums[right]nums[i])//如果满足两边之和大于第三边{countright-left;//说明nums[l1] nums[r]nums[i],...,nums[r-1] nums[r]nums[i]满足的条件的有r-l种right--;//right左移进入下一轮}else//如果nums[left]nums[right]nums[i]{left;//left右移进入下一轮}}}return count;//返回最终结果}
};
