O(n^3) can solve this prob

  • 0

    Store possible sum of two value in set (two-some)
    Init set with nums[0] + nums[1]
    Iterate rest elements of given array, nums

    Loop invariant: let nums[i] as n

    1. iterate on two-some and find nearest three-some
    2. add more two-some into set
    class Solution(object):
        def threeSumClosest(self, nums, target):
            l = len(nums)
            possible_sum_of_two_value = set() # store currently possible sum of two elements
            nearest_sum_of_three_value = None
            current_minimum_distance_to_target = float('inf')
            possible_sum_of_two_value.add(nums[0] + nums[1])
            for i in range(2, l):
                n = nums[i]
                for e in possible_sum_of_two_value:
                    if e + n == target:
                        return target
                    distance = abs(e + n - target)
                    if distance < current_minimum_distance_to_target:
                        current_minimum_distance_to_target = distance
                        nearest_sum_of_three_value = e + n
                for p in nums[:i]:
                    possible_sum_of_two_value.add(n + p)
            return nearest_sum_of_three_value

Log in to reply

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