本文共 3039 字，大约阅读时间需要 10 分钟。

Given an array nums of n integers and an integer target , are there elements a, b, c, and d in nums such that a + b + c + d = target ? Find all unique quadruplets in the array which gives the sum of target .

Notice that the solution set must not contain duplicate quadruplets.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [], target = 0Output: []

Constraints:

• 0 <= nums.length <= 200
• -109 <= nums[i] <= 109
• -109 <= target <= 109

题意：给定一个包含 n 个整数的数组 nums 和一个目标值 target ，找出所有相加等于 target 且不重复的四元组。

如果这就是面试题，我们必须思考：

• 数组索引从 0 还是从 1 开始；
• 没有解的时候怎么办，返回异常吗；
• 是否有唯一解；
• 有多个解的时候，返回哪一个解；
• 是否能够使用同一个元素两次；
• ……

本题的题目和示例给出了解答：可能没有解，返回空向量，也可能有一个或多个解；不能返回重复的四元组；同一个元素不能使用多次。

思路1 排序+双指针+去重优化

通过固定一个数 nums[i] ，可以将四元组的问题转换为三元组，使用前面的代码。同样，为了避免使用集合去重，做法是：使用连续重复元素的第一个元素，然后在后续区间内进行双指针；得到某一个解后，跳过已经使用的解元素；双指针移动时跳过重复的元素。这种做法，既顾及到了可能出现重复元素的四元组 ，也考虑到了重复使用同一元素的问题，而且避免了多次得到重复四元组。

还用到了更多的优化：

• 不符合条件时，在 lo 或者 hi 移动时跳过重复元素；
• 如果当前的固定数和后续数组最小的几个数相加，结果大于零，说明后面已经没有结果，直接退出；
• 如果当前的固定数和后续数组最大的几个数相加，结果小于零，跳过此次双指针搜索。

class Solution {
   public:    vector
   
    
     > fourSum(vector
     
      & nums, int target) {
           if (nums.size() < 4) return {
   };        vector
      
       
        > ans;        sort(nums.begin(), nums.end());   //首先排序          const int n = nums.size();        for(int i = 0; i < n - 3; ++i) {
    //只遍历到倒数第四个数为止            if (i > 0 && nums[i] == nums[i - 1]) continue; //去重优化,使用连续重复元素的第一个            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break; //后续没有解            if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; //本次无解                        int newTarget = target - nums[i];   // 将四数之和转化为三数之和                        for (int j = i + 1; j < n - 2; ++j) {
    //只遍历到倒数第三个数为止                if (j > i + 1 && nums[j] == nums[j - 1]) continue; //去重优化,使用连续重复元素的第一个                if (nums[j] + nums[j + 1] + nums[j + 2] > newTarget) break; //后续没有解                if (nums[j] + nums[n - 2] + nums[n - 1] < newTarget) continue; //本次无解                                int newTarget2 = newTarget - nums[j], lo = j + 1, hi = n - 1;   //三数之和变成两数之和                     while (lo < hi) {
    //两数之和直接套用代码                    if (nums[lo] + nums[hi] == newTarget2) {
                           ans.push_back({
   nums[i], nums[j], nums[lo], nums[hi]});                        while (lo < hi && nums[lo] == nums[lo + 1]) ++lo; //注意去重                        while (lo < hi && nums[hi] == nums[hi - 1]) --hi;                        ++lo, --hi;                    } else if (nums[lo] + nums[hi] < newTarget2) {
                           while (lo < hi && nums[lo] == nums[lo + 1]) ++lo;                        ++lo;                    } else {
                           while (lo < hi && nums[hi] == nums[hi - 1]) --hi;                        --hi;                    }                }            }        }        return ans;    }};
       
      
     
    
   

效率是可喜的：

执行用时：20 ms, 在所有 C++ 提交中击败了92.45% 的用户内存消耗：12.8 MB, 在所有 C++ 提交中击败了5.02% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108932635 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！