MENU

LeetCode15. 3Sum(对撞指针)

2019 年 02 月 16 日 • 阅读: 1924 • LeetCode阅读设置

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 会产生溢出。

参考


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