interviewalgo
, , , ,
Source
Edit
History

15. 三数之和

Introduction

Question：15. 三数之和

Analysis

TwoSum 的衍生题目。

与 TwoSum 有几个不一样的点，数组元素有重复了，求的是三元组，而且有多个解，需要返回所有解。target 固定为 0，而不是某个指定值，不需要返回 index了，而是返回值。

  1. 最简单的方法当然是直接 O(n^3) 遍历啦。
  2. 先排序，然后 遍历+二分查找，多个解可能会返回同样的解，如果筛掉？
    1. 用 set 超时。
    2. 由于遍历时，数组已经有序了，所以可以考虑跳过之前已经查找过的值了。

对比 TwoSum， threeSum 唯一一个放松的条件就是 target 固定为 0 了。

而在一个有序数组中，寻找 a + b == 0 是非常简单的，用两个指针指向数组的开头和末尾：

  • 如果 a + b > 0，则移动第一个指针
  • 如果 a + b < 0，则移动第二个指针
  • 如果 a + b == 0，则找到一个解。

将这个解法扩展到 threeSum，并加上 跳过之前查找过的值 的做法即得到最终解法。

Implement

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int moveLeft(vector<int> &nums, int left, int right) {
    left++;
    while (left < right && nums[left] == nums[left-1])
        left++;
    return left;
}
int moveRight(vector<int> &nums, int left, int right) {
    right--;
    while (left < right && nums[right] == nums[right+1])
        right--;
    return right;
}
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    int sum = 0;
    int v = INT_MIN;
    for(int i = 0;i < nums.size() && nums[i] <= 0; i++) {
        if (nums[i] == v) continue;
        int left = i + 1, right = nums.size() - 1;
        while (left < right)
        {
            sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.push_back({nums[i], nums[left], nums[right]});
                left = moveLeft(nums, left, right);
                right = moveRight(nums, left, right);
            } else if (sum < 0) {
                left = moveLeft(nums, left, right);
            } else {
                right = moveRight(nums, left, right);
            }
        }
        v = nums[i];
    }
    return res;
}