最近，在做lintcode 上的題目，有一些題還是很有意思的。這個屬于中等難度的三角形計數(shù)。
題目：

給定一個整數(shù)數(shù)組，在該數(shù)組中，尋找三個數(shù)，分別代表三角形三條邊的長度，問，可以尋找到多少組這樣的三個數(shù)來組成三角形？

首先，我們能想到的解法肯定是，將所有數(shù)組合，然后判斷。
代碼如下：

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