题目描述

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

示例 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)

• 坚持每日一题，夯实算法基础，加油！