图解两数之和的变形题之「有效三角形的个数」

点击蓝色“五分钟学算法”关注我哟

加个“星标”,天天中午 12:15,一起学算法

图解两数之和的变形题之「有效三角形的个数」

作者 | P.yh

来源 | 五分钟学算法

今天分享的题目来源于 LeetCode 上第 611 号问题:有效三角形的个数。

题目描述

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

示例 1:

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

注意:

  • 数组长度不超过1000。

  • 数组里整数的范围为 [0, 1000]。

题目解析

题目要求选出三条边,使得这三条边能够构成三角形,咋眼看上去这道题貌似和 TwoSum 没啥关系。

但我们回顾一下中学时期学的东西,三边构成三角形的条件是 任意两边之和大于第三边,那是不是说我们需要把三条边都组合配对考虑一下?其实不用,我们可以得出下面的结论

a < b < c && a + b > c => 三角形

如果已知三条边的大小顺序,那么其实我们只需要比较一次即可。

你再看看这是不是我们熟悉的 TwoSum 变种问题 – 如果题目要求找到比 target 小/大 的配对该怎么处理?

这个时候我们从右往左选定 c ,然后使用 TwoSum 来找出 a 、b 即可,由于题目只要求输出个数,那么直接相加即可。

动画描述

代码实现

public int triangleCount(int[] S) {
    if (S == null || S.length == 0) {
        return 0;
    }

    Arrays.sort(S);

    int result = 0;

    for (int i = S.length - 1; i >= 2; --i) {
        int l = 0, r = i - 1;
        while (l < r) {
            if (S[i] < S[l] + S[r]) {  // S[i] < S[l] + S[r] && S[i] > S[r] > S[l]
                result += r - l;  //  直接加上可能的个数
                r--;
            } else {
                l++;
            }
        }
    }

    return result;
}


图解 LeetCode 系列目前都同步更新在 GitHub 上面,小伙伴们在电脑端进行访问阅读:https://github.com/MisterBooo/LeetCodeAnimation


图解两数之和的变形题之「有效三角形的个数」

有热门推荐👇


1.程序员全球最厉害的 14 位程序员

2.【GitHub我在 GitHub 上看到了一个丧心病狂的开源项目!

3.【算法动画:七分钟理解什么是KMP算法

4.【数据结构十大经典排序算法动画与解析,看我就够了!


图解两数之和的变形题之「有效三角形的个数」

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 图解两数之和的变形题之「有效三角形的个数」

我还会在以下平台发布内容

GitHub 哔哩哔哩