0611. 有效三角形的個數 · ttttt

# 0611. 有效三角形的個數 ## 題目地址(611. 有效三角形的個數) <https://leetcode-cn.com/problems/valid-triangle-number/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個包含非負整數的數組，你的任務是統計其中可以組成三角形三條邊的三元組個數。示例 1: 輸入: [2,2,3,4] 輸出: 3 解釋: 有效的組合是: 2,3,4 (使用第一個 2) 2,3,4 (使用第二個 2) 2,2,3 注意: 數組長度不超過1000。數組里整數的范圍為 [0, 1000]。 ``` ``` ## 前置知識 - 排序 - 雙指針 - 二分法 - 三角形邊的關系 ## 暴力法（超時） ## 公司 - 騰訊 - 百度 - 字節 ### 思路首先要有一個數學前提： `如果三條線段中任意兩條的和都大于第三邊，那么這三條線段可以組成一個三角形`。即給定三個線段 a，b，c，如果滿足 a + b > c and a + c > b and b + c > a，則線段 a，b，c 可以構成三角形，否則不可以。力扣中有一些題目是需要一些數學前提的，不過這些數學前提都比較簡單，一般不會超過高中數學知識，并且也不會特別復雜。一般都是小學初中知識即可。 > 如果你在面試中碰到不知道的數學前提，可以尋求面試官提示試試。 ### 關鍵點解析 - 三角形邊的關系 - 三層循環確定三個線段 ### 代碼代碼支持: Python ``` <pre class="calibre18">``` class Solution: def is_triangle(self, a, b, c): if a == 0 or b == 0 or c == 0: return False if a + b > c and a + c > b and b + c > a: return True return False def triangleNumber(self, nums: List[int]) -> int: n = len(nums) ans = 0 for i in range(n - 2): for j in range(i + 1, n - 1): for k in range(j + 1, n): if self.is_triangle(nums[i], nums[j], nums[k]): ans += 1 return ans ``` ``` **復雜度分析** - 時間復雜度：O(N3)O(N ^ 3)O(N3)，其中 N 為數組長度。 - 空間復雜度：O(1)O(1)O(1) ## 優化的暴力法 ### 思路暴力法的時間復雜度為 O(N3)O(N ^ 3)O(N3)，其中 NNN 最大為 1000。一般來說， O(N3)O(N ^ 3)O(N3) 的算法在數據量 <= 500 是可以 AC 的。1000 的數量級則需要考慮 O(N2)O(N ^ 2)O(N2) 或者更好的解法。 OK，到這里了。我給大家一個干貨。應該是其他博主不太會提的。原因可能是他們不知道，也可能是他們覺得太小兒科不需要說。 1. 由于前面我根據數據規模推測到到了解法的復雜度區間是 N2N ^ 2N2, N2?logNN ^ 2 \* logNN2?logN，不可能是 NNN （WHY？）。 2. 降低時間復雜度的方法主要有： `空間換時間` 和 `排序換時間`（我們一般都是使用基于比較的排序方法）。而`排序換時間`僅僅在總體復雜度大于 O(NlogN)O(NlogN)O(NlogN) 才適用（原因不用多說了吧？）。這里由于總體的時間復雜度是 O(N3)O(N ^ 3)O(N3)，因此我自然想到了`排序換時間`。當我們對 nums 進行一次排序之后，我發現： - is\_triangle 函數有一些判斷是無效的 ``` <pre class="calibre18">``` def is_triangle(self, a, b, c): if a == 0 or b == 0 or c == 0: return False # a + c > b 和 b + c > a 是無效的判斷，因為恒成立 if a + b > c and a + c > b and b + c > a: return True return False ``` ``` - 因此我們的目標變為找到`a + b > c`即可，因此第三層循環是可以提前退出的。 ``` <pre class="calibre18">``` for i in range(n - 2): for j in range(i + 1, n - 1): k = j + 1 while k < n and num[i] + nums[j] > nums[k]: k += 1 ans += k - j - 1 ``` ``` - 這也僅僅是減枝而已，復雜度沒有變化。通過進一步觀察，發現 k 沒有必要每次都從 j + 1 開始。而是從上次找到的 k 值開始就行。原因很簡單，當 nums\[i\] + nums\[j\] > nums\[k\] 時，我們想要找到下一個滿足 nums\[i\] + nums\[j\] > nums\[k\] 的新的 k 值，由于進行了排序，因此這個 k 肯定比之前的大（單調遞增性），因此上一個 k 值之前的數都是無效的，可以跳過。 ``` <pre class="calibre18">``` for i in range(n - 2): k = i + 2 for j in range(i + 1, n - 1): while k < n and nums[i] + nums[j] > nums[k]: k += 1 ans += k - j - 1 ``` ``` 由于 K 不會后退，因此最內層循環總共最多執行 N 次，因此總的時間復雜度為 O(N2)O(N ^ 2)O(N2)。 > 這個復雜度分析有點像單調棧，大家可以結合起來理解。 ### 關鍵點分析 - 排序 ### 代碼 ``` <pre class="calibre18">``` class Solution: def triangleNumber(self, nums: List[int]) -> int: n = len(nums) ans = 0 nums.sort() for i in range(n - 2): if nums[i] == 0: continue k = i + 2 for j in range(i + 1, n - 1): while k < n and nums[i] + nums[j] > nums[k]: k += 1 ans += k - j - 1 return ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N ^ 2)O(N2) - 空間復雜度：取決于排序算法更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/a3/63/a363818092b0356fbd67882f0389528b_900x500.jpg)