有效三角形的個數
611. 有效三角形的個數 - 力扣（LeetCode）
題目描述
給定一個包含非負整數的數組 nums ，返回其中可以組成三角形三條邊的三元組個數。
示例 1:
輸入: nums = [2,2,3,4]
輸出: 3
解釋:有效的組合是:
2,3,4 (使用第一個 2)
2,3,4 (使用第二個 2)
2,2,3
示例 2:
輸入: nums = [4,2,3,4]
輸出: 4
提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
算法原理
暴力解法
用三層for 循環 枚舉出所有的三元組，根據兩邊之和大于第三邊。
優化
- 如果能構成三角形，需要滿足任意兩邊之和要大于第三邊。但是實際上只需讓較小的兩條邊
之和大于第三邊即可。 - 因此我們可以先將原數組排序，然后從小到大枚舉三元組，一方面省去枚舉的數量，另一方
面方便判斷是否能構成三角形。
源碼如下
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int n = nums.length, ret = 0;for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)for(int k = j + 1; k < n; k++)if(nums[i] + nums[j] > nums[k]) ret++;return ret;}
}
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++)for(int k = j + 1; k < n; k ++)if(nums[i] + nums[j] > nums[k])ret++;return ret;}
};
暴力這東西就是懸啊~
那么下面我們講講雙指針算法
排序+雙指針
- 首先還是將數組進行排序
- 排序完的數組是有序的，那么此時我們可以固定最長邊，然后在比這條邊小的有序數組中找二元組，使二元組之和大于最長邊。
用文字簡而言之來說就是：
- 先固定最大數
O(n) - 在最大數的左區間內，使用雙指針算法，快速統計出符合要求的三元組個數
雙指針代碼編寫
Java代碼
class Solution {public int triangleNumber(int[] nums) {// 先對數組進行排序Arrays.sort(nums);// 利用雙指針解決問題int ret = 0, n = nums.length;for(int i = n - 1; i >= 2; i--){int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
}
C++代碼
class Solution {
public:int triangleNumber(vector<int>& nums) {int ret = 0, n = nums.size();// 先排序sort(nums.begin(), nums.end());// 雙指針算法for(int i = n - 1; i >= 2; i--){int left = 0, right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){ret += right - left;right--;}else{left++;}}}return ret;}
};
