力扣18：四数之和（双指针+剪枝）-526互联

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

拿到题目最快想到的常规思路：对前两个数进行循环，后两个数用双指针，中间保证不重复

 1 class Solution
 2 {
 3 public:
 4     bool isOverflow(int x, int y) //若要判断溢出，只需判断两数同号的情况即可
 5     {
 6         if (x <= 0 && y <= 0 && x < INT32_MIN - y)
 7             return true;
 8         if (x > 0 && y > 0 && x > INT32_MAX - y)
 9             return true;
10         return false;
11     }
12     vector<vector<int>> fourSum(vector<int> &nums, int target)
13     {
14         vector<vector<int>> result;
15         if (nums.size() < 4)
16             return result;
17         sort(nums.begin(), nums.end());
18         for (int i = 0; i < nums.size() - 3; ++i)
19         {
20             if (i > 0 && nums[i] == nums[i - 1])
21                 continue;
22             for (int j = i + 1; j < nums.size() - 2; ++j)
23             {
24                 if (j > i + 1 && nums[j] == nums[j - 1])
25                     continue;
26                 int right = nums.size() - 1;
27                 for (int left = j + 1; left < nums.size() - 1; ++left)
28                 {
29                     if (left > j + 1 && nums[left] == nums[left - 1])
30                     {
31                         continue;
32                     }
33                     while (left < right)
34                     {
35                         long sum = (long)nums[i] + nums[j] + nums[left] + nums[right]; //防止溢出，先把第一个元素转成long型
36 
37                         if (sum == target)
38                         {
39                             result.push_back({nums[i], nums[j], nums[left], nums[right]});
40                             break;
41                         }
42                         else if (sum > target)
43                             right--;
44                         else
45                             break;
46                     }
47                 }
48             }
49         }
50         return result;
51     }
52 };

这个写法可以在力扣ac，但效率低了，官方题解给了如下剪枝思路。

剪枝后：

 1 class Solution
 2 {
 3 public:
 4     vector<vector<int>> fourSum(vector<int> &nums, int target)
 5     {
 6         vector<vector<int>> result;
 7         int length = nums.size();
 8         if (length < 4)
 9             return result;
10         sort(nums.begin(), nums.end());
11         for (int i = 0; i < length - 3; ++i)
12         {
13             if (i > 0 && nums[i] == nums[i - 1])
14                 continue;
15             if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
16                 break;
17             if ((long)nums[i] + nums[length - 1] + nums[length - 2] + nums[length - 3] < target)
18                 continue;
19             ;
20             for (int j = i + 1; j < length - 2; ++j)
21             {
22                 if (j > i + 1 && nums[j] == nums[j - 1])
23                     continue;
24                 if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
25                     break;
26                 if ((long)nums[i] + nums[j] + nums[length - 1] + nums[length - 2] < target)
27                     continue;
28                 int right = length - 1;
29                 for (int left = j + 1; left < length - 1; ++left)
30                 {
31                     if (left > j + 1 && nums[left] == nums[left - 1])
32                     {
33                         continue;
34                     }
35                     while (left < right)
36                     {
37                         long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
38 
39                         if (sum == target)
40                         {
41                             result.push_back({nums[i], nums[j], nums[left], nums[right]});
42                             break;
43                         }
44                         else if (sum > target)
45                             right--;
46                         else
47                             break;
48                     }
49                 }
50             }
51         }
52         return result;
53     }
54 };