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

五分钟学算法

发布于 2019-09-19 14:16:51

6740

发布于 2019-09-19 14:16:51

文章被收录于专栏：五分钟学算法五分钟学算法

作者 | 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