睢宁建网站,校园网站建设与管理,外贸商城网站开发书,济南 制作网站 公司吗1. 题目
给定一个包含非负整数的数组#xff0c;你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]…1. 题目
给定一个包含非负整数的数组你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。来源力扣LeetCode 链接https://leetcode-cn.com/problems/valid-triangle-number 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 双指针
排序固定一端剩余两个用双指针法遍历元素注意需要先固定大的端因为如果固定最小的端当不满足三角形时两个指针都可以移动来满足条件。
class Solution {
public:int triangleNumber(vectorint nums) {if(nums.size() 3)return 0;sort(nums.begin(), nums.end());int i, j, k, count 0;for(i nums.size()-1; i 2; --i){j i-1;k 0;while(k j){if(nums[k]nums[j] nums[i])// nums[i] 最大k;else{count j-k;--j;}}}return count;}
};
