611 有效三角形的个数（枚举技巧、双指针、二分查找）

我就是我 2022-09-01 09:20 145阅读 0赞

**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. 思路分析：**

分析题目可以知道我们需要枚举出所有能够构成三角形的方案，所以首先要考虑怎么样枚举才可以将所有答案枚举出来，最简单的做法是使用三层循环依次枚举三条边这样肯定可以将所有答案枚举出来，但是由于数组长度最大为10 ^ 3所以肯定会超时，所以我们考虑如何优化枚举的顺序，首先为了方便处理我们可以对数组由小到大排序，排序之后我们可以考虑枚举其中两条较大的边a, b，对于第三条边c我们需要找到最小的c使得b + c > a，因为数组是排好序的所以第三条边到第二条边的所有边长的取值都是满足条件我们将其c对应的方案数目累加到答案中即可，因为我们需要在\[0, j - 1\]的区间中找第三条边所以可以使用**双指针算法**，但是后面发现python双指针算法的代码超时了，后面修改为了java代码就通过了。除了使用双指针算法找到第三条边最小的那个位置，其实我们还可以使用**二分查找**来找到这个最小的位置，因为每一次根据中点位置对应的值可以确定答案是在当前位置的左边还是右边，使用二分就可以通过了。

**3. 代码如下：**

**二分查找：**

from typing import List
    
    
    class Solution:
        # 二分枚举出当前第三条边的位置, a, b分别表示三角形边长较大的两条边
        def binarySearch(self, nums: List[int], l: int, r: int, a: int, b: int):
            while l < r:
                # 使用位运算计算出第三条边的位置
                mid = l + r >> 1
                if b + nums[mid] > a:
                    r = mid
                else:
                    l = mid + 1
            # 这里需要判断一下求解的最小的边长c的位置是否满足b + c > a如果满足才返回r否则返回-1
            if nums[r] + b > a: return r
            else: return -1
    
        def triangleNumber(self, nums: List[int]) -> int:
            nums.sort()
            res = 0
            for i in range(2, len(nums)):
                # 只能到下标为0的位置
                for j in range(i - 1, 0, -1):
                    # 下面使用二分枚举出第三条边的位置最小的c的位置k, 那么[k:j - 1]就是合法的第三条边的取值
                    k = self.binarySearch(nums, 0, j - 1, nums[i], nums[j])
                    if k != -1: res += j - k
            return res

**双指针：**

**python代码（超时）：**

from typing import List
    
    
    class Solution:
        def triangleNumber(self, nums: List[int]) -> int:
            nums.sort()
            res = 0
            # 枚举的是较大的两条边
            for i in range(2, len(nums)):
                # 只能到下表为0的位置
                for j in range(i - 1, 0, -1):
                    # 双指针
                    k = 0
                    while k < j and nums[j] + nums[k] <= nums[i]: k += 1
                    res += j - k
            return res

**java代码：**

import java.util.Arrays;
    public class Solution {
        public int triangleNumber(int[] nums) {
            int res = 0;
            Arrays.sort(nums);
            for (int i = 2; i < nums.length; ++i){
                for (int j = i - 1; j > 0; --j){
                    int k = 0;
                    while (k < j && nums[j] + nums[k] <= nums[i]){
                        k += 1;
                    }
                    res += j - k;
                }
            }
            return res;
        }
    }