A possible O(n) python solution for twoSum


  • 0
    A

    The logic is given a list nums,
    1, we sort it, find the max and min of the sorted list

    2, using target to minus the max and min of the sorted list, to find the other min and max solution respectively,

    1. then use the min and max to remove the out of range integers in the sorted list in step 1. the remaining integers will be kept as a new list

    4, then use the new list, repeat steps 1-3, until lenght of the new list equals to two
    5, find the indices

    but i don't know how to determine the time consumption.

    Code:
    sorted_nums = sorted(nums)

        minX = target - sorted_nums[-1]
        maxX = target - sorted_nums[0]
        
        if minX + maxX == target :
            if minX == maxX :
                return self.duplicates(nums, minX)[:2]
            else :
                return [nums.index(minX), nums.index(maxX)]
        else :
            new_nums = []
            while True :
                for i in sorted_nums :
                    if i <= maxX and i >= minX :
                        new_nums.append(i)
    
                if len(new_nums) == 2 :
                    if new_nums[0] == new_nums[1] :
                        return self.duplicates(nums, new_nums[0])[:2]
                    else :
                        return sorted([nums.index(new_nums[0]), nums.index(new_nums[1])])
                else :
                    minX = target - new_nums[-1]
                    maxX = target - new_nums[0]
                    sorted_nums = new_nums
                    new_nums = []
                    
                    if minX + maxX == target :
                        if minX == maxX :
                            return self.duplicates(nums, minX)[:2]
                        else :
                            return [nums.index(minX), nums.index(maxX)]
                    else :
                        pass
    
    def duplicates(self, lst, item):
        return [i for i, x in enumerate(lst) if x == item]

Log in to reply
 

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