[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的原理去重.

    public static HashSet<ArrayList<Integer>> findAllTriAngle(int[] A) {
        HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();
        Arrays.sort(A);
        for (int i = 0; i < A.length; ++i) {
            int k = i;
            for (int j = i; j < A.length; ++j) {
                while (k < A.length && A[i] + A[j] > A[k])   // 两边之和大于第三边, k是第三边, 找第三边的最大界限
                    // two edges's sum must be larger than third edge. k is the third one
                    ++k;
                for (int l = j; l < k; l++) {
                    ArrayList<Integer> tmp = new ArrayList<Integer>();
                    tmp.add(A[i]);
                    tmp.add(A[j]);
                    tmp.add(A[l]);
                    Collections.sort(tmp);
                    result.add(tmp);
                }
            }
        }
        return result;
    }

算法思路是:

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是”平行”的.