Saturday, November 15, 2014

[LeetCode] 3Sum

Given an array S of n integers, are there elements abc in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.
    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)


思路:

题目要求的是a+b+c=0,问题可以推广到a+b+c=target。3sum问题可以转化为2sum问题:对于任意一个A[i],在数组中的其他数中解2sum问题,目标为target-A[i]。与2sum那题不同,这题要求返回的不是index而是数字本身,并且解不唯一。同时要求解排序并去重。

对排序来说,2sum中的双指针法更为方便,因为算法本身就用到排序。双指针排序法本身会去除一些重复的可能性:

(1, 2, 3, 4), target = 6
在扫描1时,解(2, 3, 4)的2sum = 5问题,找到一个解(1, 2, 3)。
在扫描2时,应当只对后面的数解2sum问题,即对(3, 4)解2sum = 4问题。这样避免再次重复找到解(1, 2, 3)。

但当存在重复数字时,光靠排序仍然无法去重:

(1, 2, 2, 2, 3, 4), target = 9
扫描第一个2时,解(2, 2, 3, 4)中的2sum=7问题,得到解(2, 3, 4)
扫描第二个2时,解(2, 3, 4)中的2sum=7问题,仍然会得到(2, 3, 4)

去除因重复数字而造成重复解有两个办法,一是将结果存到一个hash table中。由于STL的hash table (unordered_set, unordered_map)并不能为vector类型,除非自己提供一个hash function,颇为不便,也增加额外存储空间。而另一种方法就是在扫描数组时跳过重复的数字。上例中,只扫描1, 2, 3, 4来求相应的2sum问题。进一步简化,可以只扫描1, 2。因为3已经是倒数第二个数字,不可能有以它为最小数字的解。

 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
class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        return threeSumGen(num, 0);
    }
    
    vector<vector<int> > threeSumGen(vector<int> &num, int target) {
        vector<vector<int>> allSol;
        if(num.size()<3) return allSol;
        sort(num.begin(),num.end());
        for(int i=0; i<num.size()-2; i++) {
            if(i>0 && num[i]==num[i-1]) continue;
            int left=i+1, right=num.size()-1;
            while(left<right) {
                int curSum = num[left]+num[right];
                int curTarget = target-num[i];
                if(curSum==curTarget) {
                    vector<int> sol;
                    sol.push_back(num[i]);
                    sol.push_back(num[left]);
                    sol.push_back(num[right]);
                    allSol.push_back(sol);
                    left++;
                    right--;
                    while(num[left]==num[left-1]) left++;
                    while(num[right]==num[right+1]) right--;
                }
                else if(curSum<curTarget)
                    left++;
                else
                    right--;
            }
        }
        return allSol;
    }
};

总结:

这题原理上并不难,但要正确做好去重,还是要注意不少细节。红色部分的代码即为去重部分。ln 12为扫描时候的去重,ln 23-26为2sum时的去重。

2 comments:

  1. If written in Java,
    Line 25 and 26 should be:
    while (nums[left]==nums[left-1] && left<right) left++;
    while (nums[right]==nums[right+1] && left<right) right--;
    otherwise, input [0 0 0] will cause out of boundary exception.

    ReplyDelete
  2. 多谢大神赐教!!很详细爱!!!

    ReplyDelete