5fb239fd8ac7d7f82681a64473194a74
(难度Medium) Problem 15: 3Sum

Problem 15: 3Sum

链接

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

难度等级

Medium

题干

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.

题意

给定一个数组和一个target数字,要求找出三个数字a,b,c使得a+b+c=0

样例

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

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

题解

解法一: 利用2Sum

LeetCode的第一题就是2Sum问题,给定一个数组和一个target数字。要求从数组当中找到两个数的pair对,使得两个数的和等于target。

如果忘记这道题解法的同学可以看一下之前的文章:Problem 1: Two Sum - 小专栏

我们利用2Sum,只要稍稍变形,就可以解决3Sum的问题。策略也非常简单,我们枚举第一个数a[i],然后调用2Sum方法,寻找加和等于-a[i]的数对即可。

但是这样做存在一些麻烦的地方,由于数据当中存在重复的元素。所以我们需要对元素重复的情况进行过滤。

附上代码

class Solution {
public:
    vector<vector<int>> getIndex(vector<int>& nums, int target, int index) {
        map<int, int> mp;
        int n = nums.size();
        vector<vector<int>> ret;
        set<int> st;
        // 传入下标index,表示从index之后的位置开始进行2Sum
        for (int i = index+1; i < n; i++) {
            if (mp.count(target-nums[i])) {
                if (st.count(target-nums[i]) || st.count(nums[i])) continue;
                vector<int> vt;
                vt.push_back(target-nums[i]);
                vt.push_back(nums[i]);
                ret.push_back(vt);
                st.insert(nums[i]);
                st.insert(target-nums[i]);
            }
            mp[nums[i]] = i;
        }
        return ret;
    }

    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ret;
        set<pair<int, int>> st;
        set<int> s;
        for (int i = 0; i < n; i++) {
            if (s.count(nums[i])) continue;
            vector<vector<int>> tmp = getIndex(nums, -nums[i], i);
            if (tmp.size() > 0) {
                s.insert(nums[i]);
                int m = tmp.size();
                for (int j = 0; j < m; j++) {
                    vector<int> cur;
                    vector<int> nm = tmp[j];
                    cur.push_back(nums[i]);
                    cur.push_back(nm[0]);
                    cur.push_back(nm[1]);
                    sort(cur.begin(), cur.end());
                    // 判断答案是否出现过
                    if (st.count(pair<int, int>(cur[0], cur[1]))) continue;
                    st.insert(pair<int, int>(cur[0], cur[1]));
                    ret.push_back(cur);
                }
            }
        }
        return ret;
    }
};

整体的算法看起来比较机智,但是仔细分析一下就会发现,整体的复杂度是$O(n^2logn)$。我们遍历选择第一个数字的时候使用了一重循环,复杂度是$O(n)$,我们在做2Sum的时候又遍历了一次数组,多了一重循环。最后我们在判断答案是否重复的时候使用了set进行查询,set查询的复杂度是$O(logn)$。所以总体的复杂度是$O(n^2logn)$,有点超出了我们的预期。

提交之后果然结果并不理想,足足用了908ms,只超过了12.8%的人。

显然还有很大的优化空间。

解法二 正负数分组

直接使用2Sum来进行3Sum证明并不太行,为了优化算法的效率,我想到了把奇偶数分组的策略。

具体的策略也很简单,我们在通过2Sum构建3Sum的时候,其实有很多无用的多余操作。比如说当我们尝试a和b这两个正数的时候,第三个数只可能是负数。我们就没有必要遍历正数和0了。

所以我们可以把所有的数按照正负性归类,3个数加和等于0的情况其实非常有限。无非是3个0,一正两负,一正一零一负和两正一负这几种情况。我们使用2Sum对这几种情况查找可行解即可。

```
class Solution {
public:

//2 Sum
vector> getIndex(vector& nums, int target) {
map mp;
int n = nums.size();
vector> ret;
set st;
for (int i = 0; i < n; i++) { if (mp.count(target-nums[i])) { if (st.count(target-nums[i]) || st.count(nums[i])) continue; vector vt;
vt.push_back(target-nums[i]);
vt.push_back(nums[i]);
ret.push_back(vt);
st.insert(nums[i]);
st.insert(target-nums[i]);
}
mp[nums[i]] = i;
}
return ret;
}

vector> threeSum(vector& nums) {
vector neg;
vector zero;
vector posi;
set negset;
set posiset;
vector vt;
vector> ret;
int n = nums.size();
// 所有数分为0、正数和负数
for (int i = 0; i < n; i++) if (nums[i] < 0) {
neg.push_back(nums[i]);
negset.insert(nums[i]);
}
else if (nums[i] == 0) zero.push_back(0);
else {
posi.push_back(nums[i]);
posiset.insert(nums[i]);
}

top Created with Sketch.