LeetCode15. 3Sum（对撞指针）

Medium
Accepted：473,172
Submissions：2,039,197

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

链接

https://leetcode.com/problems/3sum/

题意

给定一个包含 n 个整数的数组，找到所有和为 0 的三元组（a, b, c | a + b + c = 0）。

题解

这题和 LeetCode1. Two Sum（思维）的思路一样，也就是先两重循环得到 nums[i]+nums[j]，然后再查询 -(nums[i]+nums[j]) 在不在数组内，但是难点就是不能含有同样的三元组（即两个三元组中的元素都相同），我们做的时候会出现不同的索引相同的值 -1 0 1 / 0 1 -1，那怎么解决这个问题呢？
实际上当确定了两个元素之后第三个元素也就唯一确定了，比如当 -1 0 1 确定时，其中任意两个元素不能在新的三元组出现，否则就会重复。
因此我们可以先对元素进行排序，然后一层循环找出一个值 nums [i]，再使用对撞指针的方法找另外两个元素 nums [l] 和 nums [r] 使得元素和为 0，此时如果出现了元素值相等得情况就可以对指针进行右移或左移，因为已经确定了两个元素，这样就去除了可能的重复三元组。
时间复杂度 $O (nlogn + n^2) = O (n^2)$
如果是返回不同索引的话，我们可以使用 unordered_map 加两层循环来做。

代码

Runtime: 124 ms, faster than 80.33% of C++ online submissions for 3Sum.
Memory Usage: 16.4 MB, less than 100.00% of C++ online submissions for 3Sum.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i)
        {
            if (i > 0 && nums[i] == nums[i-1]) // 后面一个元素与前面一个元素相同时，找到的三元组一样
                continue;
            int l = i + 1, r = n - 1;
            while (l < r)
            {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum > 0)
                    r--;
                else if (sum < 0)
                    l++;
                else // 找到
                {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l+1] == nums[l]) // 相同元素左指针右移
                        ++l;
                    while (l < r && nums[r-1] == nums[r]) // 右指针左移
                        --r;
                    ++l, --r;
                }
            }
        }
        return ans;
    }
};

注意在对数组进行操作时，一定要防止下标溢出，所以需要在 while 循环中加上 l < r 的限定条件，否则对于数据 0 0 0 会产生溢出。

参考

C++ two-pointes solution (easy way to handle duplicaiton).

The end.
2019 年 2 月 16 日星期六