【算法】双指针(五)-有效三角形的个数

目录

一、题目介绍

二、算法原理

1.三数验三角形

2.暴力枚举化优解

2.1分层分布数基 望枚举

2.2点算 立数基排

2.2.1点算

2.2.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 <= 1000
• 0 <= nums[i] <= 1000

二、算法原理1.三数验三角形

三数验三角形的三式 其实只要抓到那式去验 即可

a >= b >= c ：b + c ?> a —> 其实只要验它，决定性的a + b 一定> c —> 其实不用验a + c 一定> b —> 其实不用验2.暴力枚举化优解

2.1分层分布数基 望枚举成组单位个数 - 1 = 数基层数2.2点算立数基排2.2.1点算

点算 不确情况2.2.2立数基排

立数基排 能直接出结果情况 排数基

三、提交代码

class Solution { public int triangleNumber(int[] nums) { int later = nums.length - 1; Arrays.sort(nums); int ret = 0; while(later >= 2) { int left = 0; int right = later - 1; while(left < right) { if (nums[left] + nums[right] > nums[later]) { //nums[right]为数基 可直接排出结果 ret += right - left; right--; }else { //nums[left]为数基 直接排出必然非结果 left++; } } later--; } return ret; } }