基本資料#
難易度: medium 第一次嘗試：2022-11-27
- 提交紀錄：Wrong Answer → Accepted ×2
解題思路#
排序之後，三角形只要檢查兩短邊之和大於最長邊（Two Pointers 模板四）。固定最長邊 k，i 從 0、j 從 k - 1 開始：
nums[i] + nums[j] > nums[k]：i換成i..j-1任何一個都會更大，一次加j - i個，j左移。- 否則
i右移。
我的嘗試#
第一版一次加的是 j - 1（打錯），例如 [4, 7, 9]：i = 0、j = 1 時應該加 1，這版加了 0，回傳 0。
正確解法#
class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort()
res = 0
for k in range(2, len(nums)):
i, j = 0, k - 1
while i < j:
if nums[i] + nums[j] > nums[k]:
res += j - i
j -= 1
else:
i += 1
return res
複雜度#
時間 O(n²)，空間 O(1)（不算排序）。
要特別避免的錯誤#
- 一次加的是
j - i，不是j - 1。
面試口說整理#
排序後我固定最長邊，用左右指針找兩短邊：和夠大時左指針換成中間任何一個都成立，一次加上 j - i，右指針左移；不夠就左指針右移。時間 O(n²)。