-
Notifications
You must be signed in to change notification settings - Fork 0
/
16_.3Sum Closet.py
44 lines (32 loc) · 1.12 KB
/
16_.3Sum Closet.py
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.
# Return the sum of the three integers.
# You may assume that each input would have exactly one solution.
# Example 1:
# Input: nums = [-1,2,1,-4], target = 1
# Output: 2
# Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
# Example 2:
# Input: nums = [0,0,0], target = 1
# Output: 0
# Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
# Constraints:
# 3 <= nums.length <= 500
# -1000 <= nums[i] <= 1000
# -104 <= target <= 104
# Solution:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
diff = float('inf')
nums.sort()
for a in range(len(nums) - 2):
i = a + 1
j = len(nums) - 1
while i < j:
s = nums[a] + nums[i] + nums[j]
if s < target:
i = i + 1
else:
j = j - 1
if abs(s - target) < abs(diff - target):
diff = s
return diff