【双指针】有效三角形的个数

有效三角形的个数

611. 有效三角形的个数 - 力扣（LeetCode）

题目描述

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
1
2
3
4
5
6

示例 2:

输入: nums = [4,2,3,4]
输出: 4
1
2

提示:

• 1 <= nums.length <= 1000
• 0 <= 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;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

暴力这东西就是悬啊~

那么下面我们讲讲双指针算法

排序+双指针

• 首先还是将数组进行排序
• 排序完的数组是有序的，那么此时我们可以固定最长边，然后在比这条边小的有序数组中找二元组，使二元组之和大于最长边。

用文字简而言之来说就是：

• 先固定最大数 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26