算法随笔_13: 有效三角形的个数

上一篇:算法随笔_12:最短无序子数组-CSDN博客

=========================

题目描述如下:

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

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

=========================

算法思路:

首先，我们重温一下三角形三条边的关系，每两边之和大于第三边。假设三条边为e1，e2，e3。那么需要保证，e1+e2>e3，e1+e3>e2，e2+e3>e1。

那么初步能想到的算法就是通过三层循环，依次访问不同的三个数，同时判断上面的三个条件是否成立。很显然时间复杂度非常高。我们考虑一下如何优化它。

由于大量的操作是比较大小，既然是比较大小，那么我们考虑一下如果把数组排序完之后是不是能找到更优的算法呢？

我们先把数组进行升序排列。第一层循环从第一个元素开始，把它做为e1，第二层循环从第二个元素开始，把它做为e2。e3的选择肯定在e1，e2之后，由于此时数组是升序排列，因此有下面一系列的推理:

e3必定大于e1，e2，

推出e1+e3>e2，e2+e3>e1肯定成立，

推出我们只需要判断e1+e2>e3这个条件。

此时问题已经简化。但是e3也需要第三层循环吗？那样做的话，和上面的算法就一样了。此时，我们从另一个角度考虑一下这个问题。判断e1+e2>e3，是不是就相当于从e1，e2后面的元素里寻找一个特定的值e3。从某组有序的数列中查找一个特定的值，我们立刻就能想到可以使用二分查找法。

使用二分查找法的基本思想就是:

1. 我们设e1，e2后面的那个数组区间为seg。设e3的最大值为e3_max。

2. 计算得出seg的中间元素e_mid，判断e1+e2是否大于e_mid。如果小于，说明e3_max肯定不在seg区间的右半边，我们把seg重新赋值为seg区间的左半边。如果大于，说明e3_max有可能在seg区间的右半边，我们把seg重新赋值为seg区间的右半边。然后重复步骤2，直至找到e3_max。

那么e3_max的左侧所有元素均可做为e3的候选，都满足e1+e2>e3。此时，e1，e2，e3都已经找出。算法的时间复杂度为。

接下来，我们继续优化上面的算法。假设现在我们找到了第一组e1，e2，e3_max，当访问下一个e2时，下一个e3_max一定出现在当前e3_max的右侧。即，当e2递增时，e3_max也在递增。

和上面的算法类似，优化后的算法如下:

1. 我们先设个变量e3_max_ind表示e3_max的下标。

2. 我们同样使用两层循环，分别迭代e1，e2，将e3_max_ind设置为e2的下一个元素，并不断的向右寻找，直到找到最大的e3且满足e1+e2>e3，即e3_max。

3.  在第二层循环，继续访问下一个e2，此时只需要从当前的e3_max_ind处开始寻找下一个e3_max。

在两层循环完成之后，我们就找到了所有的e1，e2，e3。此算法的时间复杂度为。

实现上述算法时，要注意一些边界问题，比如: 找不到e3的情况。