三角形计数

最近，在做lintcode 上的题目，有一些题还是很有意思的。这个属于中等难度的三角形计数。
题目：

给定一个整数数组，在该数组中，寻找三个数，分别代表三角形三条边的长度，问，可以寻找到多少组这样的三个数来组成三角形？

首先，我们能想到的解法肯定是，将所有数组合，然后判断。
代码如下：

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int S[]) {
        int result = 0;
        for (int i = 0; i < S.length - 2; i++) {
            for (int j = i + 1; j < S.length - 1; j++) {
                for (int k = j + 1; k < S.length; k++) {
                    if (trigangleJudge(S[i], S[j], S[k])) {
                        result++;
                    }
                }
            }
        }
        return result;
    }
    public  boolean trigangleJudge(int a, int b, int c) {
        if (a + b > c && a + c > b && b + c > a) {
            return true;
        } else {
            return false;
        }
    }
   
}

但是永远没有最好的解决办法，所以我在网上一直想找一个更好的方法，此时看到一篇博客。其思想是，我们先找两条边，然后利用二分查找第三条边。这位前辈是用Python写的，这里我用java。很佩服他的思路。放到这里供大家借鉴思考
代码如下：

public class Solution {
    /**
     * @param S: A list of integers
     * @return: An integer
     */
    public int triangleCount(int S[]) {
     int result = 0;
        Arrays.sort(S);
        for (int i = 0; i < S.length; i++) {
            for (int j = i + 1; j < S.length; j++) {
                int l = i + 1;
                int r = j;
                int target = S[j] - S[i];
                while (l < r) {
                    int mid = (l + r) / 2;
                    if (S[mid] > target) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }

                }
                result += (j - l);
            }
        }
        return result;
    }

   
}

两份解决方案的测试结果如下：

第一种.png 第二种.png