Task: No. 16. 3Sum Closest #medium
Condition:
Given an integer array nums of length n and an integer target, find the three integers in nums whose sum is closest to the target. Returns the sum of three integers. You can assume that each input will have exactly one solution.
Solution:
def threeSumClosest(self, num, target):
num.sort()
result = num[0] + num[1] + num[2]
for i in range(len(num) - 2):
j, k = i+1, len(num) - 1
while j < k:
sum = num[i] + num[j] + num[k]
if sum == target:
return sum
if abs(sum - target) < abs(result - target):
result = sum
if sum < target:
j += 1
elif sum > target:
k -= 1
else:
return result
return result
Explanation:
Sort an array:
First we sort the num array. This will allow us to use two pointers to find the closest sum.
Initializing the result:
We initialize the result variable with the sum of the first three elements of the sorted array. This will be our starting closest amount.
Traversing the array:
We use a for loop to iterate through the array. For each element we use two pointers j and k:
j starts immediately after the current element i.
k starts from the end of the array.
Two pointers:
Inside the while loop, while j is less than k, we calculate the sum of the elements num[i], num[j] and num[k].
If sum equals target, then we return sum since we found an exact match.
Result update:
If the current sum sum is closer to target than the previous closest sum result, update result.
Pointer shift:
If sum is less than target, move pointer j to the right to increase the sum.
If sum is greater than target, shift pointer k to the left to decrease the sum.
Return result:
After completing all iterations, we return result, which will contain the sum of three numbers closest to target.
Time and space complexity:
Time complexity: O(n^2), where n is the length of the array. Sorting takes O(n log n) and the basic algorithm with two pointers runs in O(n^2).
Space complexity: O(1) since we only use a few additional variables, and do not use additional memory depending on the size of the input data.
#interview #LeetCode
🆔 @Python4all_pro