三数之和 & 最接近的三数之和

发表于 | 分类于 | 阅读次数：
本文字数： 2.5k | 阅读时长 ≈ 6 分钟

问题提出

#15 3Sum

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

#16 3Sum Closest

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

解题思路

三数之和

之前做过一道题是两数之和，做这道题时便不自觉地想要将该问题转换成两数之和的问题，大体思路是遍历数组的每一个数，以这个数的相反数为sum，采用两数之和中那个O(n)的算法求解。但是真正动手做的时候发现这样做存在着一些问题：

  • 和两数之和 不同，这道题中数组中的数可以重复，这将导致无法构造map
  • 退一步，不构造map，仍然难以处理结果中的三元组重复的问题

两数之和 题目： 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

看来只能抛弃两数之和 解题的思路。

为了保证结果不重复，排序是十分必要的。遍历排序后的数组，仍然采用上述的取相反数的思想，找剩余数之和为该数的两个数。由于数组是有序的，可以采用双指针的方法降低复杂度，这种思路和盛最多水的容器的思路很接近。为了处理数组中的重复的数，在每次迭代时，判断该数是否和前一个数相同，如果相同，则跳过该数。

另外还有一个剪枝技巧，如果当前迭代的数为正数时，整个迭代过程可以终止。

最接近的三数之和

做过三数之和之后，这道题就十分简单了，区别主要有两点：

  1. sum不是0，而是任意的；处理办法便是将上述的-nums[i]改为target-nums[i]
  2. 要求找到最接近的；处理办法是记录当前的最小值，每次找到三个数后和其比较，不断更新这个值。当然，如果差值为0，可以直接返回结果

代码

三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ret;
    sort(nums.begin(), nums.end());
    if (!nums.empty() && nums.back() < 0) return {};
    for (int k = 0; k < nums.size(); ++k) {
        if (nums[k] > 0) break;
        if (k > 0 && nums[k] == nums[k - 1]) continue;
        int target = 0 - nums[k];
        int i = k + 1, j = nums.size() - 1;
        while (i < j) {
            if (nums[i] + nums[j] == target) {
                ret.push_back({nums[k], nums[i], nums[j]});
                while (i < j && nums[i] == nums[i + 1]) ++i;
                while (i < j && nums[j] == nums[j - 1]) --j;
                ++i; --j;
            } else if (nums[i] + nums[j] < target) ++i;
            else --j;
        }
    }
    return ret;
}

最接近的三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int size = nums.size();
    int diff = INT_MAX;
    int ret = 0;
    for (int i = 0; i < size - 2; i++) {
        int new_target = nums[i] - target;
        int left = i + 1, right = size - 1;
        int sum = 0;
        while (left < right) {
            sum = new_target + nums[left] + nums[right];
            int temp = sum + target;
            if (sum == 0) return target;
            if (sum > 0) right--;
            if (sum < 0) {left++; sum = -sum;}
            if (sum < diff) {diff = sum; ret = temp;}
        }
    }
    return ret;
}

参考文章