題目內容
題目頁面: https://app.codility.com/programmers/lessons/6-sorting/triangle/
題意解析
除了任兩邊的長度必須大於第三邊之外，組成三角形的線段還有一些其他的限制：
- 三條邊的長度必須為正數。
- 任兩邊的長度之差必須小於第三邊的長度，也就是說，最長的邊的長度必須小於其他兩邊的長度之和。
- 任何一邊的長度都不能超過其他兩邊長度之和的兩倍。
如果以上任何一個條件不滿足，則無法組成三角形。
0 ≤ P < Q < R < N
解題過程
先寫一個一定會被打槍的暴力解，複雜度為O(N^3)
function solution(A) {
for (let i = 0; i < A.length; i++) {
if (A[i] > 0) {
for (let j = i + 1; j < A.length; j++) {
if (A[j] > 0) {
for (let k = j + 1; k < A.length; k++) {
if (A[k] > 0) {
if (A[i] + A[j] > A[k] &&
A[j] + A[k] > A[i] &&
A[k] + A[i] > A[j]) {
return 1;
}
}
}
}
}
}
return 0;
}
}
結果0%，，沒一個過的了，不是答案錯誤就是runtime error
直覺猜測，這一定和三角形的定義有關，查了一下谷歌大神，找到這段
當一個陣列已經排好序時，如果能夠構成三角形，那麼任意三個相鄰的元素都能構成三角形。
假設排序後的陣列為arr，元素個數為n。我們使用一個for循環遍歷arr中的元素arr[i]。由於arr已經排好序，因此arr[i]一定是arr[i]、arr[i+1]和arr[i+2]中最小的一個，arr[i+1]是中間的一個，arr[i+2]是最大的一個。如果這三個元素能夠構成三角形，那麼其他任意三個相鄰的元素也能構成三角形。
如果arr[i]+arr[i+1]>arr[i+2]，那麼一定存在一組三個相鄰的元素可以構成三角形。因此，在檢查完arr[i]、arr[i+1]和arr[i+2]之後，我們可以繼續檢查arr[i+1]、arr[i+2]和arr[i+3]，arr[i+2]、arr[i+3]和arr[i+4]，以此類推，直到遍歷完整個陣列。
總之，當一個陣列已經排好序時，只需要檢查相鄰的三個元素是否能夠構成三角形，即可判斷是否存在三個元素能夠構成三角形。這比遍歷所有可能的三元組要更高效。
所以就是要知道這個定理就可以了
function solution(A) {
A.sort((a, b) => a - b);
for (let i = 0; i < A.length - 2; i++) {
if (A[i] + A[i + 1] > A[i + 2]) {
return 1;
}
}
return 0;
}
