Leetcode 16: 3Sum Closest

https://leetcode.com/problems/3sum-closest/

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Code

import sys

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums = sorted(nums)
        min_diff = sys.maxint
         
        for i in xrange(len(nums)-2):
            j = i + 1
            k = len(nums)-1
            while j < k:
                cur_sum = nums[i] + nums[j] + nums[k]
                cur_diff = abs(cur_sum - target)
                if cur_diff < min_diff:
                     res = cur_sum
                     min_diff = cur_diff
                if cur_sum > target:
                     k -= 1
                elif cur_sum < target:
                     j += 1
                else:
                     return res

        return res

Idea

Sort the array first. Then, create three pointers, i, j and k, such that, when i is fixed, j and k are adjusted to make the 3sum approach the target. The total time complexity is O(N^2) where N is the length of nums.