題目
給定一個包含非負整數(shù)的數(shù)組?nums?，返回其中可以組成三角形三條邊的三元組個數(shù)。
示例 1:文章來源：http://www.zghlxwxcb.cn/news/detail-643602.html
輸入: nums = [2,2,3,4] 輸出: 3 解釋:有效的組合是: 2,3,4 (使用第一個 2) 2,3,4 (使用第二個 2) 2,2,3
示例 2:文章來源地址http://www.zghlxwxcb.cn/news/detail-643602.html
輸入: nums = [4,2,3,4] 輸出: 4
題解
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums); //對數(shù)組排序 增加條件
int ans = 0;
//依次枚舉每個元素 定義雙指針left和right
//如果nums[left] + nums[right] <= nums[i]則向右移動left
//nums[left]和nums[right]是小的兩個數(shù)
for (int i = 0; i < nums.length; i++) {
for (int right = i - 1, left = 0; left < right; right--) {
while (left < right && nums[left] + nums[right] <= nums[i]) {
left++;
}
//nums[left] nums[right] nums[i] 符合答案
//第一個元素換成nums[left + 1]...nums[right - 1] 依然符合答案
//所以個數(shù)為right-1-left+1=right-left
ans += right - left;
}
}
return ans;
}
}到了這里，關于每日一題 611有效三角形的個數(shù)（相向雙指針）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
