給定一個(gè)包含非負(fù)整數(shù)的數(shù)組，你的任務(wù)是統(tǒng)計(jì)其中可以組成三角形三條邊的三元組個(gè)數(shù)。示例 1:輸入: [2,2,3,4] 輸出: 3 解釋: 有效的組合是: 2,3,4 (使用第一個(gè) 2) 2,3,4 (使用第二個(gè) 2) 2,2,3思路:1. 數(shù)組排序，便于后序的處理 2. 固定最長(zhǎng)的邊c，然后采用雙指針在其左側(cè)尋找合適的 a、b:1) a從最左側(cè)開始(nums[0])2) b從最右側(cè)開始(nums[i-1])3. 如果nums[left] + nums[right] > nums[i]，說明[left,right]、 [left+1,right]...[right-1,right] 均滿足條件，以 nums[right] 為中間邊的情況已全部考慮過，然后 right -= 14. 如果nums[left] + nums[right] <= nums[i]，兩邊之和太小，需要增大，left += 1class Solution:def triangleNumber(self, nums: List[int]) -> int:# 1. 排序nums.sort()# 2. 遍歷count = 0for i in range(2, len(nums)):left = 0right = i - 1while left < right:if nums[left] + nums[right] > nums[i]:count += (right - left)right -= 1else:left += 1return count

總結(jié)

以上是生活随笔為你收集整理的7. Leetcode 611. 有效三角形的个数 (数组-双向双指针)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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