LC 611. 有效三角形的个数

题目描述

这是 LeetCode 上的 611. 有效三角形的个数 ，难度为 中等。

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

示例 1:

1
2
3
4
5
6
7
8
9
输入: [2,2,3,4]

输出: 3

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

注意:

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

基本分析

根据题意，是要我们统计所有符合 $nums[k] + nums[j] > nums[i]$ 条件的三元组 $(k,j,i)$ 的个数。

为了防止统计重复的三元组，我们可以先对数组进行排序，然后采取「先枚举较大数；在下标不超过较大数下标范围内，找次大数；在下标不超过次大数下标范围内，找较小数」的策略。

排序 + 暴力枚举

根据「基本分析」，我们可以很容易写出「排序 + 三层循环」的实现。

image.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    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 >= 0; j--) {
                for (int k = j - 1; k >= 0; k--) {
                    if (nums[j] + nums[k] > nums[i]) ans++;
                }
            }
        }
        return ans;
    }
}

  • 时间复杂度：排序时间复杂度为 $O(n\log{n})$；三层遍历找所有三元祖的复杂度为 $O(n^3)$。整体复杂度为 $O(n^3)$
  • 空间复杂度：$O(\log{n})$

排序 + 二分

根据我们以前讲过的的 优化枚举的基本思路，要找符合条件的三元组，其中一个切入点可以是「枚举三元组中的两个值，然后优化找第三数的逻辑」。

我们发现，在数组有序的前提下，当枚举到较大数下标 $i$ 和次大数下标 $j$ 时，在 $[0, j)$ 范围内找的符合 $nums[k’] + nums[j] > nums[i]$ 条件的 $k’$ 的集合时，以符合条件的最小下标 $k$ 为分割点的数轴上具有「二段性」。

令 $k$ 为符合条件的最小下标，那么在 $nums[i]$ 和 $nums[j]$ 固定时，$[0,j)$ 范围内：

  • 下标大于等于 $k$ 的点集符合条件 $nums[k’] + nums[j] > nums[i]$；
  • 下标小于 $k$ 的点集合不符合条件 $nums[k’] + nums[j] > nums[i]$。

因此我们可以通过「二分」找到这个分割点 $k$，在 $[k,j)$ 范围内即是固定 $j$ 和 $i$ 时，符合条件的 $k’$ 的个数。

image.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    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 >= 0; j--) {
                int l = 0, r = j - 1;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (nums[mid] + nums[j] > nums[i]) r = mid;
                    else l = mid + 1;
                }
                if (l == r && nums[r] + nums[j] > nums[i]) ans += j - r;
            }
        }
        return ans;
    }
}

  • 时间复杂度：排序时间复杂度为 $O(n\log{n})$；两层遍历加二分所有符合条件的三元组的复杂度为 $O(n^2\log{n})$。整体复杂度为 $O(n^2\log{n})$
  • 空间复杂度：$O(\log{n})$

排序 + 双指针

更进一步我们发现，当我们在枚举较大数下标 $i$，并在 $[0, i)$ 范围内逐步减小下标（由于数组有序，也就是逐步减少值）找次大值下标 $j$ 时，符合条件的 $k’$ 必然是从 $0$ 逐步递增（这是由三角不等式 $nums[k] + nums[j] > nums[i]$ 所决定的）。

因此，我们可以枚举较大数下标 $i$ 时，在 $[0, i)$ 范围内通过双指针，以逐步减少下标的方式枚举 $j$，并在遇到不满足条件的 $k$ 时，增大 $k$ 下标。从而找到所有符合条件三元组的个数。

image.png

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    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, k = 0; k < j; j--) {
                while (k < j && nums[k] + nums[j] <= nums[i]) k++;
                ans += j - k;
            }
        }
        return ans;
    }
}

  • 时间复杂度：排序时间复杂度为 $O(n\log{n})$，双指针找所有符合条件的三元组的复杂度为 $O(n^2)$。整体复杂度为 $O(n^2)$
  • 空间复杂度：$O(\log{n})$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.611 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。