3Sum Closest
Given an array of integers, find the sum of three numbers that is closest to the target value. You may assume that each input would have exactly one solution.
Constraints:
- 3 <= nums.length <= 10^3
- -10^15 <= nums[i] <= 10^15
- -10^15 <= target <= 10^15
Examples:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum of -1, 1 and 2 is 2, which is closest to the target value of 1.
Solutions
Two Pointers
The two pointers approach involves sorting the array first and then using two pointers to find the closest sum. The outer loop iterates over the array, and the inner loop uses two pointers, one starting from the next element of the outer loop and one from the end of the array. The sum of the three elements is calculated, and if it is closer to the target than the current closest sum, the closest sum is updated.
public int threeSumClosest(int[] nums, int target) {
int closestSum = Integer.MAX_VALUE;
for (int i = 0;
i < nums.length - 2;
i++) {
for (int j = i + 1;
j < nums.length - 1;
j++) {
for (int k = j + 1;
k < nums.length;
k++) {
int sum = nums[i] + nums[j] + nums[k];
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
}
}
}
}
return closestSum;
}Follow-up:
How would you optimize the solution to have a better time complexity?
