解法一(暴力求解)(会超时)O(nlogn+n3)
class Solution {
public:
int triangleNumber(vector<int>& nums) {
// 1. 排序
sort(nums.begin(), nums.end());
int n = nums.size(), ret = 0;
// 2. 从小到大枚举所有的三元组
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(n2)
class Solution
{
public:
int triangleNumber(vector<int>& nums)
{
// 1. 优化,排序一下数组
sort(nums.begin(), nums.end());
// 2. 利用双指针解决问题
int ret = 0, n = nums.size();
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;
}
};