Day57 | 灵神 | 相向双指针：四数之和&&有效三角形的个数

18.四数之和

18. 四数之和 - 力扣（LeetCode）

思路：

在三数之和的基础上再套了一层循环

i在最外层，然后对i去重

j，l，r就是三数之和的代码

区别在于：

1.对于第二个数字num[j]的去重：因为j是从i+1开始的，而j对j的去重只能是在j自己的遍历过程中，即，当j大于i+1时，这说明j-1>i，说明此时去重不会让j==i的情况给去掉了

2.如果数组大小小于4那就没必要列举了

3.leetcode增大了数值，要使用long long防止溢出

主要是防止四个数字相加时的溢出，所以四个数字相加时至少得有一个是long long类型

完整代码：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        if(nums.size()<4)
            return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-3;i++)
        {
            long long a=nums[i];
            if(i&&nums[i]==nums[i-1])   continue;
            for(int j=i+1;j<nums.size()-2;j++)
            {
                if (j>i+1&&nums[j]==nums[j-1]) continue; // 跳过重复数字
                int l=j+1,r=nums.size()-1;
                while(l<r)
                {
                    long long x=a+nums[j]+nums[l]+nums[r];
                    if(x>target)
                        r--;
                    else if(x<target)
                        l++;
                    else
                    {
                        res.push_back({nums[i],nums[j],nums[l],nums[r]});
                        for(l++;l<r&&nums[l]==nums[l-1];l++);
                        for(r--;l<r&&nums[r]==nums[r+1];r--);
                    }
                }
            }
        }
        return res;
    }
};

611.有效三角形的个数

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

思路：

还是和两数之和三数之和一样的思路，只是判定条件不同，本题是利用两数之和大于第三边的性质来做。

三角形三边 a，b，c a<b<c

把最大的一边（c）当做固定边，通过 比较a+b和c的大小来确定指针的移动

i是c的下标，a的下标是l，b的下标是r

从末尾往前遍历i，相当于从大到小遍历i

每次都在[0,i-1]范围内遍历l和r，即对l和r进行加减操作

只要 a + b > c 说明找到了一个合法方案，res++，并且大的指针减小（r–）继续查找合法方案

否则的话，说明a + b < c 那说明 a太小了，那就 l++

易错点

不可以有思维惯性，两数之和和三数之和都是固定最小的i，从前往后遍历

但是本题固定最小边却行不通

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res=0;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size()-2;i++)
        {
            int l=i+1,r=nums.size()-1;
            while(l<r)
            {
                if(nums[i]+nums[l]>nums[r])
                {
                    res+=(r-l);
                    break;
                }
                else if(nums[i]+nums[l]==nums[r])
                    l++;
                else
                    r--;
            }
        }
        return res;
    }
};

原因在于，当我们固定最小边a的时候，我们会遇到 a + b == c的情况

但是这种情况下我们a是固定的，那这种情况下指针一定有可能是b太小了，那就是往大的移动，那就是l++，但是也有可能是c太大了，那就是r–

但是我们在else if(nums[i]+nums[l]==nums[r])这个条件判定中不可以即写l++又写r–，因为这样的话肯定会漏掉一些合理的答案

但是我们也不能只写l++和r–其中的一个，因为不管写哪个都会漏掉另外一种的情况，这样还是得不到正确答案

而正确做法的固定最大边c就不同了，a + b > c的时候就说明是b大了移动b就行

a + b <= c的时候就说明是a小了，移动a就行

关键就是：指针的移动不能出现二义性，不能往这边移动也行往那边移动也行，这样的话一定会漏掉另外一种情况

完整代码：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int res=0;
        sort(nums.begin(),nums.end());
        for(int i=nums.size()-1;i>=2;i--)
        {
            int l=0,r=i-1;
            while(l<r)
            {
                if(nums[r]+nums[l]>nums[i])
                {
                    res+=(r-l);
                    r--;
                }
                else
                    l++;
            }
        }
        return res;
    }
};