拿到Amazon面试,发一题3Sum

刚才收到了Amazon的面试邮件,第二个面试了,第一个没去…完了…题刷不完了…得突突刷了.

这个题最先想到的是用hashtable,然后写出来发现TLE过不了,最开始各种优化,虽然剪枝不少,但是根基太差,我甚至把内置的sorted()方法弃用改用快排.果然都是没效果.

后来改成了左右两边向中间移动的方式才AC

3Sum

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:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, abc)
  • 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)

Attempt1:(TLE)

View Code PYTHON
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
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution:
    # @return a list of lists of length 3, [[val1,val2,val3]]
    def threeSum(self, num):
        def genHashtable(num):
            max_num = -num[0]
            min_num = -num[len(num)-1]
            hastable = {}
            for i,a in enumerate(num):
                if i > 0 and a == num[i-1]:
                    continue
                for j,b in enumerate(num[i+1:]):
                    if j > 0 and b == num[j+i]:
                        continue
                    sum2 = a + b
                    if sum2 < min_num or sum2 > max_num:
                        continue
                    else:
                        if sum2 in hastable:
                            hastable[sum2] += [(j+i+1,[a,b])]
                        else:
                            hastable[sum2] = [(j+i+1,[a,b])]
            return hastable
 
        def qsort(arr): 
            if len(arr) <= 1:
                return arr
            else:
                return qsort([x for x in arr[1:] if x<arr[0]]) + [arr[0]] + qsort([x for x in arr[1:] if x>=arr[0]])
 
        length = len(num)
 
        if length<=3:
            return [qsort(num)] if length == 3 and sum(num) == 0 else []
 
        num = qsort(num)
        #print num
        twosumtable = genHashtable(num)
        #print twosumtable
        ret = []
        last_c = None
        for k,c in enumerate(num[2:]):
            if c < 0 or k+3 < length and c == num[k+3]:
                continue
            if -c in twosumtable:
                for e in twosumtable[-c]:
                    #print -c,e[0],k+2
                    if e[0] < k+2:
                        ret += [e[1] + [c]]
        return ret

 

Attempt2:(AC)

View Code PYTHON
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
class Solution:
    # @return a list of lists of length 3, [[val1,val2,val3]]
    def threeSum(self, num):
        length = len(num)
 
        if length<=3:
            return [sorted(num)] if length == 3 and sum(num) == 0 else []
 
        num = sorted(num)
        ret = []
        for i in range(0,length-2):
            if i>0 and num[i] == num[i-1]:
                continue
            j,k = i + 1, length - 1
            twoSum = 0 - num[i]
            while j < k:
                if num[j] + num[k] < twoSum:
                    j += 1
                elif num[j] + num[k] == twoSum:
                    ret += [[num[i],num[j],num[k]]]
                    j+=1
                    k-=1
                    while j < k and num[j] == num[j-1]:
                        j += 1
                    while k > j and num[k] == num[k+1]:
                        k -= 1
                else:
                    k -= 1
        return ret

 

Share This: 

Leave a Reply

Your email address will not be published. Required fields are marked *