Accepted Python 3 O(n) Solution (pointers and "sorted dict")


  • 0
    S
    def two_sum(nums, target):
        if (len(nums) == 2 and sum(nums) != target) or len(nums) < 2:
                return []
        # 1. create list of dicts, each containing pre-sort info
        nums_info = nums_to_dict(nums)
    
        # 2. sort nums_info by key, 'num'
        nums_info = sorted(nums_info, key=lambda k: k['num'])
    
        i = 0; j = len(nums_info) - 1
        while i < j:
            num1 = nums_info[i].get('num')
            num2 = nums_info[j].get('num')
            _sum = num1 + num2
            if _sum == target:
                # 3. once matched return original idx from nums_info
                return [nums_info[i].get('idx'), nums_info[j].get('idx')]
            if _sum > target:
                j -= 1
            else:
                i += 1
    
        return []
    
    
    def nums_to_dict(nums):
        nums_info = []
        for (idx, elem) in enumerate(nums):
            ptr = ref(elem)
            dict = {'ptr':ptr, 'num':ptr.get(), 'idx': idx}
            nums_info.append(dict)
        return nums_info
    
    class ref:
        def __init__(self, obj):
            self.obj = obj
        def get(self):
            return self.obj
        def set(self, obj):
            self.obj = obj
    

Log in to reply
 

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