【LeetCode】有效三角形的个数 Java 题解

关注

发布于: 刚刚

题目描述

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

示例 1:

输入: [2,2,3,4]输出: 3解释:有效的组合是: 2,3,4 (使用第一个 2)2,3,4 (使用第二个 2)2,2,3
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-triangle-number著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

这个题目题意容易理解，判断三条边能组成三角形的条件为：任意两边之和大于第三边，任意两边之差小于第三边。
如何能快速判断满足三角形的条件呢？对数组类题目来说，排序是降低时间复杂度最常用的方法。
将题目三条边进行升序排序，使它们满足 a ≤ b ≤ c,那么 a + c > b 和 b + c > a 一定成立的，我们只需要保证 a + b > c。通过升序排序，大大降低了算法查找的时间复杂度。
在代码中使用了 Arrays.sort() 排序方法。 Arrays.sort()基本类型数组使用快速排序, 对于对象类型，使用归并排序。归并排序的时间复杂度是 n * log n, 快速排序的平均时间复杂度也是 n *log n，但是归并排序的需要额外的 n 个引用的空间。

通过代码

    public int triangleNumber(int[] nums) {        int n = nums.length;        Arrays.sort(nums);        int ans = 0;        for (int i = 0; i < n; i++) {            for (int j = i + 1; j < n; j++) {                int left = j + 1, right = n - 1, k = j;                while (left <= right) {                    int mid = left + (right - left) / 2;                    if (nums[i] + nums[j] > nums[mid]) {                        k = mid;                        left = mid + 1;                    } else {                        right = mid - 1;                    }                }                ans += k - j;            }        }        return ans;    }

复制代码

总结

二分查找解法的时间复杂度是 O(n * n * n), 空间复杂度是 O(1)
坚持每日一题，夯实算法基础，加油！

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/a8a91249b3c11cb6aa9934fcd】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】有效三角形的个数 Java 题解

题目描述

思路分析

通过代码

总结

HQ数字卡

评论