企业网站建完后没人,软件开发费用计算方法,个人网站内容如何填写,手机网站建设讯息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;}
};
