2 题目描述
1.3 题目示例
1.4 算法思路
- 我们首先得清除构成三角形的条件：两边之和大于第三边，两边之差小于第三边，但是要验证这两个条件好像很麻烦，有没有更简单的方法呢？
- 当三个数
a，b，c我们从小到大排序：然后你会发现只需要满足a + b > c就能构成一个有效的三角形。 - 在排序后的数组中，我们固定最大的边
nums[k]作为三角形的第三边，然后在[0, k-1]范围内使用对撞指针寻找满足条件的两边。
- 具体来说，设置
left = 0和right = k-1。当nums[left] + nums[right] > nums[k]时，由于数组是升序排列，left到right-1的所有位置与当前right组成的配对都能满足条件。这时我们可以直接给计数器增加right - left个有效组合，然后将right左移一位。 - 如果
nums[left] + nums[right] <= nums[k]，说明当前的两边之和太小，需要增大其中一边。由于right已经是当前范围内较大的值，我们通过将left右移来增加两边之和。
1.5 核心代码
代码语言：javascript
AI代码解释
#include<iostream> #include<vector> #include<algorithm> using namespace std; class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end());//升序排序 int n = nums.size();//n为数组大小 int ret = 0; for (int i = n - 1; i >= 2; i--)//因为最少三条边，所以i>=2 { int left = 0, right = i - 1; while (left < right) { if (nums[left] + nums[right] > nums[i]) { ret += right - left; right--; } else { left++; } } } return ret; } };1.6 示例测试（总代码）
代码语言：javascript
AI代码解释
#include<iostream> #include<vector> #include<algorithm> using namespace std; class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end());//升序排序 int n = nums.size();//n为数组大小 int ret = 0; for (int i = n - 1; i >= 2; i--)//因为最少三条边，所以i>=2 { int left = 0, right = i - 1; while (left < right) { if (nums[left] + nums[right] > nums[i]) { ret += right - left; right--; } else { left++; } } } return ret; } }; int main() { vector<int> nums1 = { 4,2,3,4 }; cout << Solution().triangleNumber(nums1) << endl; return 0; }在这里插入图片描述
