Leetcode(15) 3Sum

发表于 | 更新于 | 分类于

Description:

Given an array _S_ of _n_ integers, are there elements _a_, _b_, _c_ in _S_ 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.

For example, given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]

解法：

参考：http://blog.csdn.net/u010656539/article/details/52204607

首先，两数和问题这样做。先对数组中的数进行排序，再设置两个指针，一个指向头，一个指向尾。判断两数和是否等于想要的数，如果是则在结果集添加这个数组；如果小了说明左边指针指向的数小了，因此左指针右移；反之如果大了则右指针左移。 尝试把三数和问题转化为两数和问题：同样先对数组排序，设置三个指针p,q,r，p指针指向第一个数x，则q,r要指向数组中剩余数中的两个，并且指向的两数和为-x，从而转化为两数和问题。对p指向第一个数的情况分析完毕后，不可能再有满足题意且包含x的情况，于是p右移。这样一直分析到p指向数组中倒数第三个数的情况。注意跳过所有重复的情况。 代码如下：

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:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort();
        res = [];
        i = 0;
        while(i<len(nums)-2):
            r = [];
            r.append(nums[i]);
            sum = 0 - nums[i];
            p = i + 1;
            q = len(nums) - 1;
            while(p<q):
                if(nums[p] + nums[q] == sum):
                    r.append(nums[p]);
                    r.append(nums[q]);
                    res.append(r);
                    r = [];
                    r.append(nums[i]);
                    p+=1;
                    q-=1;
                    while(p<q and nums[p] ==nums[p-1]):
                        p+=1;
                    while(p<q and nums[q] == nums[q+1]):
                        q-=1;
                elif(nums[p] + nums[q] < sum):
                    p+=1;
                else:
                    q-=1;
            while(i<len(nums)-2 and nums[i+1] == nums[i]):
                i+=1;
            i+=1;
        return res;