有效三角形的个数( LeetCode 611 )

一、题目描述

给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:

输入: [2,2,3,4]
输出: 3
解释:
有效的组合是
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

  1. 数组长度不超过1000。
  2. 数组里整数的范围为 [0, 1000]。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效三角形的个数(611):https://leetcode-cn.com/problems/valid-triangle-number/ 
class Solution {
    public int triangleNumber(int[] nums) {

        // 先将数组排序
        Arrays.sort(nums);

        // 获取数组的长度
        int n = nums.length;

        // 统计可以组成三角形三条边的三元组个数,一开始为 0 
        int res = 0;

        // 通过两个循环来定位三角形的两边
        // 其中 nums[i] 为能形成三角形的三边中的最短边,因此 i 的范围为 [ 0 , n - 3 ]
        for (int i = 0; i < n - 2; i++) {

            // 其中 nums[j] 为能形成三角形的三边中的较短边,因此 j 的范围为 [ i + 1 , n - 2 ]
            for (int j = i + 1; j < n - 1; j++) {

                // nums 已经排好序,并且 i < j,因此 nums[i] < nums[j]
                // 判断三条边能组成三角形的条件为:假设三条边长从小到大为 a < b < c ,当且仅当 a + b > c 这三条边能组成三角形。
                // nums[i] 为 a,nums[j] 为 b,先计算出最短边和较短边之和
                int sum = nums[i] + nums[j];

                // 接下来,在 [ j + 1 , n - 1 ] 这个区间去寻找出最长边 c 

                // left 为当前区间最左侧的元素,可以获取到
                int left = j + 1;

                // right 为当前区间最右侧的元素,可以获取到
                int right = n - 1;

                // 在 while 循环里面,left 不断的 ++,而 right 不断的 --
                // 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
                // 即当 left = right + 1 时,搜索区间没有元素了
                // 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
                // 所以此时 while 循环的判断可以使用等号
                while (left <= right) {

                    // left + (right - left) / 2 和 (left + right) / 2 的结果相同
                    // 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
                    // 比如数据 int 的最大值为 2,147,483,647
                    // 此时,left 为 2,147,483,640
                    // 此时,right 为 2,147,483,646
                    // 两者直接相加超过了 2,147,483,647,产生了溢出
                    int mid =  left + (right - left) / 2;

                    // 两边之和大于中间元素的值,说明两边之和肯定大于 [ left , mid ] 这个区间中所有的元素
                    // 因此[ left , mid ] 这个区间中所有的元素都和 nums[i]、nums[j] 构成三角形
                    if (sum > nums[mid]) {

                        // 因此,缩小查找区间为 [ mid + 1 , right]
                        // 查看一下 [ mid + 1 , right] 是否也有元素可以和 nums[i]、nums[j] 构成三角形
                        left = mid + 1;

                    // 两边之和小于中间元素的值,说明两边之和肯定小于 [ mid , right ] 这个区间中所有的元素
                    // 因此 [ mid ,right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
                    }else if(sum < nums[mid] ) {

                        // 因此,缩小查找区间为 [ left , mid - 1]
                        // 此时,舍弃掉了 [ mid ,right]
                        right = mid - 1;

                    // 两边之和等于中间元素的值,和两边之和小于中间元素的值情况是一样的
                    // 说明两边之和肯定小于或者等于 [ mid , right ] 这个区间中所有的元素
                    // 因此 [ mid ,right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
                    }else if( sum == nums[mid] ){
                        // 因此,缩小查找区间为 [ left , mid - 1]
                        // 此时,舍弃掉了 [ mid ,right]
                        right = mid - 1; 
                    }
                }

                // 来到这一步的时候,left = right + 1
                // 如果此时两边之和大于了 right 指向的值 nums[right]
                // 那么由于数组有序,并且 i < j < right
                // 因此 nums[i] < nums[j] < nums[right],也就是说 nums[i] 、nums[j] 、 nums[right] 可以构成三角形
                // 并且 [ j + 1 , right ] 这个区间中所有的元素都可以和 nums[i] 、nums[j] 构成三角形
                if (sum > nums[right] ) {

                    // 计算 [ j + 1 , right ] 这个区间中所有的元素
                    int ans = right - (j + 1) + 1;

                    // 这些元素都能和 nums[i] 、nums[j] 构成三角形,把结果累加上去
                    res += ans;
                }
            }
        }

        // 返回结果
        return res;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效三角形的个数(611):https://leetcode-cn.com/problems/valid-triangle-number/ 
class Solution {
public:
    int triangleNumber(vector<int>& nums) {

        // 先将数组排序
        sort(nums.begin(), nums.begin() + nums.size());

        // 获取数组的长度
        int n = nums.size();

        // 统计可以组成三角形三条边的三元组个数,一开始为 0 
        int res = 0;

        // 通过两个循环来定位三角形的两边
        // 其中 nums[i] 为能形成三角形的三边中的最短边,因此 i 的范围为 [ 0 , n - 3 ]
        for (int i = 0; i < n - 2; i++) {

            // 其中 nums[j] 为能形成三角形的三边中的较短边,因此 j 的范围为 [ i + 1 , n - 2 ]
            for (int j = i + 1; j < n - 1; j++) {

                // nums 已经排好序,并且 i < j,因此 nums[i] < nums[j]
                // 判断三条边能组成三角形的条件为:假设三条边长从小到大为 a < b < c ,当且仅当 a + b > c 这三条边能组成三角形。
                // nums[i] 为 a,nums[j] 为 b,先计算出最短边和较短边之和
                int sum = nums[i] + nums[j];

                // 接下来,在 [ j + 1 , n - 1 ] 这个区间去寻找出最长边 c 

                // left 为当前区间最左侧的元素,可以获取到
                int left = j + 1;

                // right 为当前区间最右侧的元素,可以获取到
                int right = n - 1;

                // 在 while 循环里面,left 不断的 ++,而 right 不断的 --
                // 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
                // 即当 left = right + 1 时,搜索区间没有元素了
                // 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
                // 所以此时 while 循环的判断可以使用等号
                while (left <= right) {

                    // left + (right - left) / 2 和 (left + right) / 2 的结果相同
                    // 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
                    // 比如数据 int 的最大值为 2,147,483,647
                    // 此时,left 为 2,147,483,640
                    // 此时,right 为 2,147,483,646
                    // 两者直接相加超过了 2,147,483,647,产生了溢出
                    int mid =  left + (right - left) / 2;

                    // 两边之和大于中间元素的值,说明两边之和肯定大于 [ left , mid ] 这个区间中所有的元素
                    // 因此[ left , mid ] 这个区间中所有的元素都和 nums[i]、nums[j] 构成三角形
                    if (sum > nums[mid]) {

                        // 因此,缩小查找区间为 [ mid + 1 , right]
                        // 查看一下 [ mid + 1 , right] 是否也有元素可以和 nums[i]、nums[j] 构成三角形
                        left = mid + 1;

                    // 两边之和小于中间元素的值,说明两边之和肯定小于 [ mid , right ] 这个区间中所有的元素
                    // 因此 [ mid ,right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
                    }else if(sum < nums[mid] ) {

                        // 因此,缩小查找区间为 [ left , mid - 1]
                        // 此时,舍弃掉了 [ mid ,right]
                        right = mid - 1;

                    // 两边之和等于中间元素的值,和两边之和小于中间元素的值情况是一样的
                    // 说明两边之和肯定小于或者等于 [ mid , right ] 这个区间中所有的元素
                    // 因此 [ mid ,right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
                    }else if( sum == nums[mid] ){
                        // 因此,缩小查找区间为 [ left , mid - 1]
                        // 此时,舍弃掉了 [ mid ,right]
                        right = mid - 1; 
                    }
                }

                // 来到这一步的时候,left = right + 1
                // 如果此时两边之和大于了 right 指向的值 nums[right]
                // 那么由于数组有序,并且 i < j < right
                // 因此 nums[i] < nums[j] < nums[right],也就是说 nums[i] 、nums[j] 、 nums[right] 可以构成三角形
                // 并且 [ j + 1 , right ] 这个区间中所有的元素都可以和 nums[i] 、nums[j] 构成三角形
                if (sum > nums[right] ) {

                    // 计算 [ j + 1 , right ] 这个区间中所有的元素
                    int ans = right - (j + 1) + 1;

                    // 这些元素都能和 nums[i] 、nums[j] 构成三角形,把结果累加上去
                    res += ans;
                }
            }
        }

        // 返回结果
        return res;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 有效三角形的个数(611):https://leetcode-cn.com/problems/valid-triangle-number/ 
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:

        # 先将数组排序
        nums.sort()

        # 获取数组的长度
        n = len(nums)

        # 统计可以组成三角形三条边的三元组个数,一开始为 0 
        res = 0

        # 通过两个循环来定位三角形的两边
        # 其中 nums[i] 为能形成三角形的三边中的最短边,因此 i 的范围为 [ 0 , n - 3 ]
        for i in range( 0 , n - 2 ):

            # 其中 nums[j] 为能形成三角形的三边中的较短边,因此 j 的范围为 [ i + 1 , n - 2 ]
            for j in range( i + 1 , n - 1 ):

                # nums 已经排好序,并且 i < j,因此 nums[i] < nums[j]
                # 判断三条边能组成三角形的条件为:假设三条边长从小到大为 a < b < c ,当且仅当 a + b > c 这三条边能组成三角形。
                # nums[i] 为 a,nums[j] 为 b,先计算出最短边和较短边之和
                sum = nums[i] + nums[j]

                # 接下来,在 [ j + 1 , n - 1 ] 这个区间去寻找出最长边 c 

                # left 为当前区间最左侧的元素,可以获取到
                left = j + 1

                # right 为当前区间最右侧的元素,可以获取到
                right = n - 1

                # 在 while 循环里面,left 不断的 ++,而 right 不断的 --
                # 当 [ left , right ] 这个区间不存在元素的时候,才跳出 while 循环,也就是当 left > right 时跳出循环
                # 即当 left = right + 1 时,搜索区间没有元素了
                # 由于 left 和 right 相遇的时候指向同一个元素,这个元素是存在于 [ left , right] 区间,这个区间就一个元素
                # 所以此时 while 循环的判断可以使用等号
                while  left <= right :

                    # left + (right - left) / 2 和 (left + right) / 2 的结果相同
                    # 但是使用 left + (right - left) / 2 可以防止由于 left 、right 同时太大,导致相加的结果溢出的问题
                    # 比如数据 的最大值为 2,147,483,647
                    # 此时,left 为 2,147,483,640
                    # 此时,right 为 2,147,483,646
                    # 两者直接相加超过了 2,147,483,647,产生了溢出
                    mid =  left + (right - left) // 2

                    # 两边之和大于中间元素的值,说明两边之和肯定大于 [ left , mid ] 这个区间中所有的元素
                    # 因此[ left , mid ] 这个区间中所有的元素都和 nums[i]、nums[j] 构成三角形
                    if  sum > nums[mid] :

                        # 因此,缩小查找区间为 [ mid + 1 , right]
                        # 查看一下 [ mid + 1 , right] 是否也有元素可以和 nums[i]、nums[j] 构成三角形
                        left = mid + 1

                    # 两边之和小于中间元素的值,说明两边之和肯定小于 [ mid , right ] 这个区间中所有的元素
                    # 因此 [ mid ,right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
                    elif sum < nums[mid] :

                        # 因此,缩小查找区间为 [ left , mid - 1]
                        # 此时,舍弃掉了 [ mid ,right]
                        right = mid - 1

                    # 两边之和等于中间元素的值,和两边之和小于中间元素的值情况是一样的
                    # 说明两边之和肯定小于或者等于 [ mid , right ] 这个区间中所有的元素
                    # 因此 [ mid ,right] 这个区间中所有的元素和 nums[i]、nums[j] 无法构成三角形
                    elif sum == nums[mid] :
                        # 因此,缩小查找区间为 [ left , mid - 1]
                        # 此时,舍弃掉了 [ mid ,right]
                        right = mid - 1 

                # 来到这一步的时候,left = right + 1
                # 如果此时两边之和大于了 right 指向的值 nums[right]
                # 那么由于数组有序,并且 i < j < right
                # 因此 nums[i] < nums[j] < nums[right],也就是说 nums[i] 、nums[j] 、 nums[right] 可以构成三角形
                # 并且 [ j + 1 , right ] 这个区间中所有的元素都可以和 nums[i] 、nums[j] 构成三角形
                if  sum > nums[right] :

                    # 计算 [ j + 1 , right ] 这个区间中所有的元素
                    ans = right - (j + 1) + 1

                    # 这些元素都能和 nums[i] 、nums[j] 构成三角形,把结果累加上去
                    res += ans


        # 返回结果
        return res

四、动画理解(没有声音)

隐藏内容
  • 普通用户购买价格:不可购买
  • 会员用户购买价格:999积分
  • 永久会员用户购买价格:免费推荐