【优选算法】——Leetcode——611. 有效三角形的个数

目录

​编辑

1.题目 

2 .补充知识

3.解法⼀（暴⼒求解）（可能会超时）：

算法思路：

 算法代码：

 4.解法⼆（排序+双指针）：

算法思路：

 以输入: nums = [4,2,3,4]为例​编辑

​ 5.代码实现

1.C语言

2.C++

---

1.题目 

611. 有效三角形的个数

给定一个包含非负整数的数组 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

2 .补充知识

三个数构成三角形的条件

假设三条边长度为：a, b, c

则构成三角形的条件要同时满足以下条件：

a+b>c

a+c>b

b+c>a

若已知

则只需满足a+b>c就可以

3.解法⼀（暴⼒求解）（可能会超时）：

算法思路：

三层fo循环枚举出所有的三元组，并且判断是否能构成三⻆形。

虽然说是暴⼒求解，但是还是想优化⼀下：
判断三⻆形的优化：

▪ 如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。

▪ 因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅⾯⽅便判断是否能构成三⻆形。

 算法代码：

 
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;
    }
};

 4.解法⼆（排序+双指针）：

算法思路：

先将数组排序。

根据「解法⼀」中的优化思想，我们可以固定⼀个「最⻓边」，然后在⽐这条边⼩的有序数组中找出⼀个⼆元组，使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的，我们可以利⽤「对撞指针」来优化。

设最⻓边枚举到 i 位置，区间[left, right] 是 i 位置左边的区间（也就是⽐它⼩的区间）：

◦ 如果nums[left] + nums[right] > nums[i] ：
▪ 说明[left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐nums[i] ⼤的⼆元组
▪ 满⾜条件的有 right - left 种
▪ 此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进⼊下⼀轮判断

◦ 如果nums[left] + nums[right] <= nums[i] ：
▪ 说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满⾜条件
的⼆元组
▪ left 位置的元素可以舍去， left++ 进⼊下轮循环

 以输入: nums = [4,2,3,4]为例

right-- 

 C移位

 5.代码实现

1.C语言

void quick_sort(int arr[], int left, int right)
{
    if (left < right)
    {
        int i = left, j = right, pivot = arr[left];
        while (i < j)
        {
            while (i < j && arr[j] >= pivot) j--;
            if (i < j) arr[i++] = arr[j];
            while (i < j && arr[i] < pivot) i++;
            if (i < j) arr[j--] = arr[i];
        }
        arr[i] = pivot;
        quick_sort(arr, left, i - 1);
        quick_sort(arr, i + 1, right);
    }
}
 
int triangleNumber(int* nums, int numsSize){
    // 1. 优化
 quick_sort(nums,0,numsSize-1); // 排序
    // 2. 利⽤双指针解决问题
    int ret = 0;
    for (int i = numsSize - 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;
}
 

2.C++

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;
    }
};