AlgoPressAppearance
0611-有效三角形的个数
题目描述
https://leetcode.cn/problems/valid-triangle-number
给定一个包含非负整数的数组 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
思路：回溯法（超时）
将数字排列，从第一个数字还是选取，当选到3个的时候，就计算是否满足三角形的条件 a+b>c 满足则 count ++ ，因为每个数字都需要递归遍历，会超时
csharp
public class Solution {
int count = 0;
private void dfs(int[] nums, int index, List<int> list){
if(list.Count == 3){
if(list[0] + list[1] > list[2]){
count++;
}
return ;
}
if(index >= nums.Length){
return;
}
//选他
list.Add(nums[index]);
dfs(nums,index+1,list);
list.RemoveAt(list.Count-1);
//不选他
dfs(nums,index+1,list);
}
public int TriangleNumber(int[] nums) {
Array.Sort(nums);
List<int> list = new List<int>();
dfs(nums,0,list);
return count;
}
}
思路：双指针
将数组排序，固定最后一个数字，然后前面用双指针指向前后。
csharp
public class Solution{
int count = 0;
public int TriangleNumber(int[] nums){
Array.Sort(nums);
for(int i=nums.Length-1; i>=2; i--){
int left = 0;
int right = i-1;
while(left < right){
if(nums[right] + nums[left] > nums[i]){
count += right - left; //注意这里累加的是个数 (right-left) 不是+=1
right--;
}
else{
left++;
}
}
}
return count;
}
}