[Google] Given an array of Integer, return all valid triangles 给一个int数组, 返回所有可能的三角形

这个题目好像有很多变种, 比如给一个int数组, 返回所有的不重复数字组成的三角形, 或者返回所有等腰/直角三角形. 反正就是多几个限制和少几个限制. 我遇到的这个是返回所有的可能的三角形, 这其中包含:等边,等腰等等, 只要是Valid就可以.

传统解法就是O(n^3)的暴力, 当然, 这肯定不是我们想要的. 就不多说了.

说到三角形,基本看懂中文的都知道两个特性:

  1. 两边之和大于第三边
  2. 两边之差小于第三边

对于一个已经排序的数组, 我们用第一条就可以了. 证明:

Assume,x,y,z are three int, 0<x<=y<=z, if z < x-y, then y+z < x (against to 1), so z < x-y false

最后, 我们还要去重, 因为数组会有{4,4,4}, 所以要把选出的三边排序一下, 然后用HashSet的原理去重.

算法思路是:

  1. 双指针i和j, i扫全部, j从i开始往后扫
  2. 每次j扫的时候, 用k往前扫到可能的所有边.
  3. 然后sort一下这些边, 放进result里

这个是O(n^2)的算法, 在第二个for loop里, 虽然有一个while和一个for, 但是他们的开始点是k, 而k每次从i开始, 所以是O(n^2), 如果不理解,可以这样想, k虽然在j里面做循环, 但是开始时,j和k的值是一样的, 都是i, 所以虽然k是nest 循环, 但是和j是”平行”的.