C语言每日一题（65）有效三角形的个数

题目链接

题目链接

题目描述

给定一个包含非负整数的数组 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 <= 1000
• 0 <= nums[i] <= 1000

思路分析

知识点：双指针

解析： 

这里补充一个数学知识，判断三个数能否构成三角形的条件是，任意两边之和大于第三边，任意两边之差小于第三边。

我们可以将这个条件再优化一下，先将这三个数a,b,c从小到大排一下序，目前a<b<c，任意两边之和大于第三边，即a+b>c,a+c>b,b+c>a,但如果已经知道c是最大的情况后，我们只需要判断a+b>c即可，因为c最大，它随便加一个正数肯定比a和b大，所以不需要考虑了。

任意两边之差小于第三边，即b-a<c,c-b<a,c-a<b,当你满足上面的条件后，这个条件也自然而然就满足了。

步骤

1.根据上面思路，我们先将所给数组进行升序排序，最大值就在最右边。

2.从最右边开始，将最大数保留（下标称为max），随后定义两个指针在[0，max-1]范围内找到满足和大于max的两个数。

3.这两个指针下标分别为left，right。当nums[left]+nums[right]>nums[max]时，说明这两个数是符合条件的，并且不止一组，这是已经排过序的数组，如果nums[left]+nums[right]>nums[max]，说明left+1到right都是满足的，而且个数就是right-left，只需比较一次就能找出许多情况，非常高效。此时将right--，去判断下一个区间。

如果nums[left]+nums[right]<=nums[max],说明此时left可以进行下移，因为此时right最大条件都不满足，那移动right指针没有意义，此时应该移动的是left。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ret = 0;
        for (int i = nums.size() - 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;
    }
};