提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

文章目录

前言

一、有效三角形的个数（medium）

1.1、题目

1.2、讲解算法原理

1.3、编写代码

二、和为s的两个数字

2.1、题目

2.2、讲解算法原理

2.3、编写代码

三、三数之和

3.1、题目

3.2、讲解算法原理

3.3、编写代码

四、四数之和

4.1、题目

4.2、讲解算法原理

4.3、编写代码

总结

---

---

前言

世上有两种耀眼的光芒，一种是正在升起的太阳，一种是正在努力学习编程的你!一个爱学编程的人。各位看官，我衷心的希望这篇博客能对你们有所帮助，同时也希望各位看官能对我的文章给与点评，希望我们能够携手共同促进进步，在编程的道路上越走越远！

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、有效三角形的个数（medium）

1.1、题目

1.2、讲解算法原理

补充数学知识：给我们三个数，判断是都能够构成三角形。

步骤：利用单调性，使用双指针算法来解决问题。

1. 先固定最大的数；
2. 在最大的数的左区间内，使用双指针算法，快速统计出符合要求的三元组的个数。

来举例一个区间[2，2，3，4，4，9，10]来说明一下情况：

• 优化：先对整个数组排序，用于固定最大的数。
• 我们根据三角形的满足条件得出的两个结论：因为数组是升序的，所以设a和b为最小的两边，c为最大的边，a + b > c就能构成三角形；a + b <= c便不能构成三角形。
• 我们使用双指针的思想，假设数组的下标为指针，设left指针指向数组下标为0的位置，设right指针指向数组中最大的数的左区间中的最大值。

1. 拿上面的数组为例，先固定最大的数为10，设left为第一个2所在的位置，right为9所在的位置，left + right大于10，因为是升序，所以当right不变，left指向2~9之间的任意数时，都符合三角形的条件，因此得出的结论：下标right - left的值为满足三角形的情况，9所在的位置可以划掉，right--。
2. 此时left为第一个2，right为5，最大值依旧为10：2 + 5 < 10，不构成三角形的条件，left++，再次判断三角形的条件，重复操作，直到left和right相遇，最大值为10所在的情况查看完毕，更新最大值。

1.3、编写代码

class Solution 
{
public:
    int triangleNumber(vector<int>& nums) 
    {
        // 先进行排序
        sort(nums.begin(), nums.end());

        // 利用双指针解决问题
        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;
    }
};

二、和为s的两个数字

2.1、题目

2.2、讲解算法原理

利用单调性，使用双指针算法解决问题。

举一个数组[2，7，11，15，19，21]，t = 30为例：设left指针指向2，right指针指向21，让两数相加来和t值(30)比较。

分为三种情况：

1. sum < t：left为2，right为21，相加得23 < t(30)，因为数组为递增顺序，left和right区间的数字都比21要小，因此划掉2，left++；
2. sum > t：left为11，right为21，相加得32 > t(30)，left和right区间的数值都比left(11)要大，因此划掉21，right--；
3. sum = t(30)：返回结果。

2.3、编写代码

class Solution 
{
public:
    vector<int> twoSum(vector<int>& price, int target) 
    {
        int left = 0,right = price.size() - 1;
        while(left < right)
        {
            if(price[left] + price[right] > target)
            {
                right--;
            }
            else if(price[left] + price[right] < target)
            {
                left++;
            }
            else
            {
                return {price[left],price[right]};
            }
        }
        // 照顾编译器
        return {-1,-1};
    }
};

三、三数之和

3.1、题目

3.2、讲解算法原理

步骤：

1. 排序；
2. 固定一个数a；(小优化：对于下面的数组来说，a > 0之后，不管left 和 right 两个指针指向哪里，和 a 相加之后，都不会等于0，因此 a > 0之后，就可以结束了)
3. 在该固定的数a后面的区间内，利用“双指针算法”快速找到两个的和等于 -a 即可。

处理细节问题：

1、去重；

• 找到一种结果之后，left 和 right 指针要跳过重复元素；
• 当使用完一次双指针算法之后，i 也需要跳过重复的元素；
• 避免越界。

2、不漏；

• 找到一种结果之后，不要“停”，缩小区间，继续寻找。

3.3、编写代码

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        vector<vector<int>> ret;// 定义一个二级数组用于储存数组

        // 排序
        sort(nums.begin(), nums.end());
        int i = 0, n = nums.size();
        // 固定一个数a
        for(i = 0; i < n; ) // for()循环中初始化、判断和调整这三个部分都可以写为空
        {
            // 小优化
            if(nums[i] > 0) break;
            int left = i + 1, right = n - 1, target = -nums[i];// target两个指针所指向的数相加==固定数的负数
            while(left < right)
            {
                int sum = nums[left] + nums[right];
                if(sum > target) right--;
                else if(sum < target) left++;
                else 
                {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++, right--;
                    // 去重操作 left right
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i++;
            // 去重操作 i
            while(i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
};

四、四数之和

4.1、题目

4.2、讲解算法原理

排序 + 双指针：

1. 依次固定一个数a；
2. 在 a 后面的区间内，利用"三数之和"找到三个数，使这三个数的和等于 target -a 即可。

三数之和：

1. 依次固定一个数 b；
2. 在 b 后面的区间内，利用"双指针"找到两个数，使这两个数的和等于 target - a - b 即可。

处理细节问题：

1、去重；

• 找到一种结果之后，left 和 right 指针要跳过重复元素；
• 当使用完一次双指针算法之后，i 也需要跳过重复的元素；
• 避免越界。

2、不漏；

• 找到一种结果之后，不要“停”，缩小区间，继续寻找。

4.3、编写代码

class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        // 定义一个二级数组，用来存放数组
        vector<vector<int>> ret;

        // 排序
        sort(nums.begin(),nums.end());

        // 固定一个数a
        int i = 0,n = nums.size();
        for(i = 0; i < n; )
        {
            // 固定数b ---> 将四数求和转换成三数求和
            for(int j = i + 1; j < n; )
            {
                // 利用双指针的算法
                int left = j + 1, right = n -1; 
                while(left < right)
                {
                    // 这个地方用int类型，有可能会超出int的范围，用long long
                    long long aim = (long long)target - nums[i] - nums[j];
                    int sum = nums[left] + nums[right];
                    if(sum > aim) right--;
                    else if(sum < aim) left++;
                    else
                    {
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        left++, right--;
                        // 去重操作 left right
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right+1]) right--;
                    }
                }
                j++;
                // 去重操作 j
                while(j < n && nums[j] == nums[j-1]) j++;
            }
            i++;
            // 去重操作 i
            while(i < n && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }
};

---

总结

好了，本篇博客到这里就结束了，如果有更好的观点，请及时留言，我会认真观看并学习。
不积硅步，无以至千里；不积小流，无以成江海。