文章目錄

• • 1 題目
  • 2 解決方案
  • • 2.1 思路
    • 2.2 時(shí)間復(fù)雜度
    • 2.3 空間復(fù)雜度
  • 3 源碼

1 題目

題目：三角形計(jì)數(shù)（Triangle Count）
描述：給定一個(gè)整數(shù)數(shù)組，在該數(shù)組中，尋找三個(gè)數(shù)，分別代表三角形三條邊的長(zhǎng)度，問(wèn)，可以尋找到多少組這樣的三個(gè)數(shù)來(lái)組成三角形？

lintcode題號(hào)——382，難度——medium

樣例1：

輸入: [3, 4, 6, 7] 輸出: 3 解釋: 可以組成的是 (3, 4, 6), (3, 6, 7),(4, 6, 7)

樣例2：

輸入: [4, 4, 4, 4] 輸出: 4 解釋:任何三個(gè)數(shù)都可以構(gòu)成三角形，所以答案為 C(3, 4) = 4

2 解決方案

2.1 思路

??首先三條邊在滿足a<=b<=c的前提下，只要滿足a+b>c即可構(gòu)成三角形，這樣我們先對(duì)數(shù)組進(jìn)行排序，使得按照位置取出來(lái)的三個(gè)數(shù)能夠滿足a<=b<=c，將c通過(guò)循環(huán)進(jìn)行遍歷固定，再在c位置之前的子數(shù)組中找到和的值大于c的兩個(gè)數(shù)即可。

2.2 時(shí)間復(fù)雜度

??排序的時(shí)間復(fù)雜度O(n * log n)，外層循環(huán)的時(shí)間復(fù)雜度為O(n)，在子數(shù)組找兩數(shù)和大于目標(biāo)值的數(shù)的時(shí)間復(fù)雜度為O(n)，總時(shí)間復(fù)雜度為O(n^2)。

2.3 空間復(fù)雜度

??空間復(fù)雜度為O(1)。

3 源碼

細(xì)節(jié)：

形成三角形的三邊條件為(a<b<c && a+b>c)即可。

先進(jìn)行排序，讓有序取出的abc滿足a<b<c，再固定c去判斷a+b>c（下標(biāo)遍歷固定c，再two sum之前的區(qū)間）

若a+b比c大，則b不動(dòng)，a右移的所有a+b都大于c，加入結(jié)果之后，b左移進(jìn)行下一輪

若a+b比c小，則需要a左移，進(jìn)行下一輪

C++版本：

/** * @param S: A list of integers * @return: An integer */ int triangleCount(vector<int> &S) {// write your code hereint result = 0;if (S.empty()){return result;}// 先排序，確保三個(gè)數(shù)的大小 a<=b<=csort(S.begin(), S.end());// 固定c的位置for (int i = 2; i < S.size(); i++){int target = S.at(i);int temp = twoSumGreater(S, 0, i - 1, target); // 找到子數(shù)組中令兩數(shù)和大于目標(biāo)值的結(jié)果個(gè)數(shù)result += temp;}return result; }// left指向a，right指向b，找到令 a+b>c 的結(jié)果 int twoSumGreater(vector<int> & S, int left, int right, int target) {int result = 0;while (left < right){if (S.at(left) + S.at(right) <= target){left++;}else if(S.at(left) + S.at(right) > target){result = result + (right - left); // 直接將left左移的所有結(jié)果加入right--;}}return result; }

總結(jié)

以上是生活随笔為你收集整理的69 三角形计数（Triangle Count）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。