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

• 2019 年 10 月 5 日
• 筆記

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