四数之和【leetcode 18】

四数之和【leetcode 18】

解答 排序 + 双指针

解题思想：在三数之和的基础上多一层循环即可。

#include 
#include 
using namespace std;

class Solution {
public:
    vector> fourSum(vector& nums, int target) {
        vector> result;
        int n = nums.size();
        if (n < 4) return result; // 特判

        sort(nums.begin(),nums.end()); // 排序
        // 选取第一个数
        for (int i = 0; i < n-3; i++)
        {
            if(i>0&&nums[i]==nums[i-1]) continue; // 去重

            if (i+3 target) // 剪枝
                break;
            if (n-3>i&&(long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) // 剪枝
                continue;
            // 选取第二个数
            for (int j = i+1; j < n-2; j++)
            {
                if(j>i+1&&nums[j]==nums[j-1]) continue;// 去重

                if(j+2 target) // 剪枝
                    break;
                if (n-2>j&&(long)nums[i] + nums[j] + nums[n-2] + nums[n-1] < target) // 剪枝
                    continue; 
                // 通过双指针取第三个和第四个数
                int left=j+1;
                int right = n-1;
                while (lefttarget)
                    {
                        right--;// 此两数之和太大，右指针左移
                    }
                    else
                    {
                        left++; // 此两数之和太小，左指针右移
                    }
                }
                
            }
            
        }
        return result;
    }
};