• 18.四数之和 :::info 对于15.三数之和 (opens new window)双指针法就是将原本暴力O(n^3)的解法，降为O(n^2)的解法，四数之和的双指针解法就是将原本暴力O(n^4)的解法，降为O(n^3)的解法。 ::: 对比
      四数相加

    代码：（详细注释）

    1. class Solution {
    2. public:
    3.     vector<vector<int>> fourSum(vector<int>& nums, int target) {
    4.         vector<vector<int>> result;
    5.         sort(nums.begin(), nums.end());
    6.         for (int k = 0; k < nums.size(); k++) {
    7.             // 这种剪枝是错误的，这道题目target 是任意值，主要是负数，越加越小。
    8.             // if (nums[k] > target) {
    9.             //     return result;
    10.             // }
    11.             // 去重
    12.             if (k > 0 && nums[k] == nums[k - 1]) {
    13.                 continue;
    14.             }
    15.             for (int i = k + 1; i < nums.size(); i++) {
    16.                 // 正确去重方法
    17.                 if (i > k + 1 && nums[i] == nums[i - 1]) {
    18.                     continue;
    19.                 }
    20.                 int left = i + 1;
    21.                 int right = nums.size() - 1;
    22.                 while (right > left) {
    23.                     //其实就是 nums[k] + nums[i] + nums[left] + nums[right] > target
    24.                     // 只不过是为了防止溢出
    25.                     if (nums[k] + nums[i] > target - (nums[left] + nums[right])) {
    26.                         right--;
    27.                     } else if (nums[k] + nums[i] < target - (nums[left] + nums[right])) {
    28.                         left++;
    29.                     } else {
    30.                         result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
    31.                         // 去重逻辑应该放在找到一个四元组之后
    32.                         while (right > left && nums[right] == nums[right - 1]) right--;
    33.                         while (right > left && nums[left] == nums[left + 1]) left++;
    35.                         // 找到答案时，双指针同时收缩
    36.                         right--;
    37.                         left++;
    38.                     }
    39.                 }
    41.             }
    42.         }
    43.         return result;
    44.     }
    46. };

    分析：
    经典二分查找