鱼爪网商城网站如何建设,外包做网站价格,手机商城怎么下载,成都全网营销推广有效三角形的个数
611. 有效三角形的个数 - 力扣#xff08;LeetCode#xff09;
题目描述
给定一个包含非负整数的数组 nums #xff0c;返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2…有效三角形的个数
611. 有效三角形的个数 - 力扣LeetCode
题目描述
给定一个包含非负整数的数组 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 10000 nums[i] 1000
算法原理
暴力解法
用三层for 循环 枚举出所有的三元组根据两边之和大于第三边。
优化
如果能构成三角形需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边 之和大于第三边即可。因此我们可以先将原数组排序然后从小到大枚举三元组一方面省去枚举的数量另一方 面方便判断是否能构成三角形。
源码如下
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int n nums.length, ret 0;for(int i 0; i n; i)for(int j i 1; j n; j)for(int k j 1; k n; k)if(nums[i] nums[j] nums[k]) ret;return ret;}
}class Solution {
public:int triangleNumber(vectorint nums) {sort(nums.begin(), nums.end());int n nums.size(), ret 0;for(int i 0; i n; i)for(int j i 1; j n; j)for(int k j 1; k n; k )if(nums[i] nums[j] nums[k])ret;return ret;}
};暴力这东西就是悬啊~
那么下面我们讲讲双指针算法
排序双指针
首先还是将数组进行排序排序完的数组是有序的那么此时我们可以固定最长边然后在比这条边小的有序数组中找二元组使二元组之和大于最长边。 用文字简而言之来说就是
先固定最大数 O(n)在最大数的左区间内使用双指针算法快速统计出符合要求的三元组个数
双指针代码编写
Java代码
class Solution {public int triangleNumber(int[] nums) {// 先对数组进行排序Arrays.sort(nums);// 利用双指针解决问题int ret 0, n nums.length;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--;}else{left;}}}return ret;}
}C代码
class Solution {
public:int triangleNumber(vectorint nums) {int ret 0, n nums.size();// 先排序sort(nums.begin(), nums.end());// 双指针算法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--;}else{left;}}}return ret;}
};
