专题一 -双指针 - leetcode 611. 有效三角形的个数 | 中等难度

leetcode 611. 有效三角形的个数 | 中等难度

1. 题目详情

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

1. 原题链接

leetcode 611. 有效三角形的个数

2. 基础框架

● Cpp代码框架

class Solution {
public:
    int triangleNumber(vector<int>& nums) {

    }
};

2. 解题思路

1. 题目分析

$(1)$ 题目要求数组nums中所有的满足构成三角形的三个数的组合个数。
$(2)$ 对于a/b/c三边，构成三角形的条件是任意两边之和大于第三边：
a+b>c&&a+c>b&&b+c>a

2. 算法原理

$(1)$ 首先呢先想到暴力解法：三层for循环依次确定三个边a/b/c，并判断a+b>c&&a+c>b&&b+c>a，都满足了计数才自增；时间复杂度O(n^3)，直接提交leetcode不给过。
进行优化：先对数组nums排序，对于有序的数组而言，依次确定数组左边的较小得数a/b，c在a/b之后确定。此时可以满足关系：a <= b <= c；故a+b>c&&a+c>b&&b+c>a中a+c>b和b+c>a是一定成立的，就不用再判断了，减少两次判断，此时就可以通过了。时间复杂度还是O(n^3)。
$(2)$ 解法二：借助有序数组的单调性解题。
还是先对数组nums进行排序，满足关系：a <= b <= c；

$(3)$

3. 时间复杂度

暴力解法 ：$O(n^3)$

对撞双指针：$O(n^2)$

利用单调性，外层循环确定一个数，内层循环确定两个数，减少一层循环。

3. 代码实现

解法一：暴力搜索（也叫遍历）

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // a+b>c a+c>b b+c>a
        int cnt = 0;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        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]
                    // && nums[i] + nums[k] > nums[j]
                    // && nums[j] + nums[k] > nums[i]){
                    if(nums[i] + nums[j] > nums[k]){
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
};

解法二：对撞双指针

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 结果计数
        int cnt = 0;
        int n = nums.size();
        // 排序
        sort(nums.begin(), nums.end());
        for(int i = n - 1; i >= 0; i--){
            // 对撞双指针
            int l = 0, r = i - 1;
            while(l < r){
                int sum = nums[l] + nums[r];
                
                if(sum > nums[i]){
                    // a+b>c
                    cnt += r - l;
                    r--;
                }
                else{
                    // a+b<=c
                    l++;
                }
            }
        }
        return cnt;
    }
};

4. 知识与收获

$(1)$ 感受双指针对时间复杂度的降维能力把。

$The$ $End$