每天一道算法题【蓝桥杯】【四数之和】

思路

固定一个数转化为三数之和问题
再固定一个数转化为两数之和问题

注意

两数之和target2=target-a-b
target2和target都要设成long long类型避免超限

#define _CRT_SECURE_NO_WARNINGS 1
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());//先排序降低时间复杂度

        int n = nums.size();

        int a = 0, b = a + 1, left = b + 1, right = n - 1;//先固定a，其他三数之和等于target-a
        //再固定b，使得四数之和变成两数之和的问题，两数之和等于target-a-b
        long long t2 = 0;//注意t2可能会因为target-a-b超出int范围，故使用long long类型
        while (a <= n - 4)
        {
            b = a + 1, left = b + 1, right = n - 1;
            while (b <= n - 3)
            {
                t2 = (long long)target - nums[a] - nums[b];//注意t2可能会因为target-a-b超出int范围，故使用long long类型强制转换target
                left = b + 1, right = n - 1;
                while (left < right)
                {
                    if (nums[left] + nums[right] < t2) left++;
                    else if (nums[left] + nums[right] > t2) right--;
                    else
                    {
                        ret.push_back({ nums[a],nums[b],nums[left],nums[right] });//找到结果后插入ret数组
                        left++; right--;//使得找到一个结果之后接着找
                        while (left < right && nums[left] == nums[left - 1])left++;
                        while (left < right && nums[right] == nums[right + 1])right--;//跳过重复的数
                    }
                }
                b++;
                while (b < left && nums[b] == nums[b - 1])b++;//跳过重复的数
            }
            a++;
            while (a < b && nums[a] == nums[a - 1])a++;//跳过重复的数
        }
        return ret;

    }
};