最近，在做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;
}
}
}
但是永遠沒有最好的解決辦法砚哗，所以我在網(wǎng)上一直想找一個更好的方法龙助，此時看到一篇博客。其思想是蛛芥，我們先找兩條邊提鸟，然后利用二分查找第三條邊。這位前輩是用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
