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).
解法：
同三数和的解法，用三个指针移动遍历各种可能性。代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class :
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort();
i = 0;
dis = 233333333;
while(i < len(nums) - 2):
p = i + 1;
q = len(nums) - 1;
remain = target - nums[i];
while(p<q):
if(abs(remain - nums[p] - nums[q]) < dis):
dis = abs(remain - nums[p] - nums[q]);
result = nums[i] + nums[p] + nums[q];
if(nums[p] + nums[q] == remain):
return target;
elif(nums[p] + nums[q] < remain):
p+=1;
else:
q-=1;
i+=1;
return result;
|
近期评论