https://leetcode.com/problems/3sum-closest/
16. 3Sum Closest
- Total Accepted: 97996
- Total Submissions: 324135
- Difficulty: Medium
- Contributors: Admin
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
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
.