A way to solve it not using dictionary, time complexity O(nlogn) for sorting, double pointers


  • 0
    K
        def twoSum(self, nums, target):
            nums_n = [e for e in enumerate(nums)]
            nums_n.sort(key = lambda a: a[1])
            l, r = 0, len(nums_n) - 1
            while l < r:
                if nums_n[l][1] + nums_n[r][1] < target:
                    l += 1
                elif nums_n[l][1] + nums_n[r][1] > target:
                    r -= 1
                else:
                    return sorted([nums_n[l][0]+1, nums_n[r][0]+1])

  • 0

    Rewrote it a bit.

    def twoSum(self, nums, target):
        nums, indexes = zip(*sorted((n, i) for i, n in enumerate(nums, 1)))
        l, r = 0, len(nums) - 1
        while l < r:
            if nums[l] + nums[r] < target:
                l += 1
            elif nums[l] + nums[r] > target:
                r -= 1
            else:
                return sorted([indexes[l], indexes[r]])

Log in to reply
 

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