3Sum solution in Python using dict


  • 0
    K

    I use the dictionary to solve this problem. There are mainly 3 parts for my code.

    • convert nums list into dict
    • use dict to select some specific cases like all elements being zero [0, 0, 0] or two elements being the same while the left element is -2 times of it. such as [2, 2, -4].
    • extract the keys of the dict and sort them in ascending order. then use one for loop to loop over each key of the dict.

    The codes are as below:

            num_dic = {}
            for num in nums:
                if num in num_dic:
                    num_dic[num] += 1 
                else:
                    num_dic[num] = 1
            tri_list = []
            N = len(num_dic)
            
            for key in num_dic.keys():
                if key != 0:
                    if num_dic[key] >= 2:
                        if num_dic.has_key(-2*key):
                            tri_list.append([key, key, -2*key])
                elif num_dic[0] >= 3:
                    tri_list.append([0, 0, 0])
                
            keys = sorted(num_dic.keys())
            k0 = N -1
            if N >= 3:
                for i in range(0, N-2):
                    target = -keys[i]
                    j = i + 1
                    k = k0
                    while j < k:
                        comp = target - keys[j]
                        while keys[k] >= comp and j < k:
                            if keys[k] == comp:
                                tri_list.append([keys[i], keys[j], comp])
                            k -= 1
                        if j == i + 1:
                            k0 = k
                        j += 1
                    if k0 - i < 2:
                        break
            return tri_list
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.