问题描述
https://leetcode.com/problems/3sum-closest/
解决思路
和15题很像！
- sort array
- use base to represent the first number, left points the second and right points the right
- calculate the sum of them, if sum less than target, then move left pointer to right. If sum more than target, then move right pointer to left
- traverse all of them, then move base to the next, and repeat the process mentioned above.
- during all the process, record the sum when the closest distance occurs
代码
class Solution {
public int threeSumClosest(int[] nums, int target) {
//1. sort array
//2. use base to represent the first number, left points the second
//and right points the right
//3. calculate the sum of them, if sum less than target, then move left
//pointer to right. If sum more than target, then move right pointer to left
//4. traverse all of them, then move base to the next, and repeat the process
//mentioned above.
//5. during all the process, record the sum when the closest distance occurs
int distance = 0;
int i = 0;
int sum = 0;
int min = Integer.MAX_VALUE;
int res = 0;
//corner case
if(nums.length < 2) return Integer.MAX_VALUE;
Arrays.sort(nums);
while(i < nums.length - 2){
int leftPointer = i + 1;
int rightPointer = nums.length - 1;
int base = nums[i];
//traverse of situations under this base
while(leftPointer < rightPointer){
sum = base + nums[leftPointer] + nums[rightPointer];
distance = Math.abs(sum - target);
int preMin = min;
min = Math.min(min, distance);
if(preMin != min) {
res = sum;
}
if(sum < target){
leftPointer = moveLeft(nums, leftPointer + 1, rightPointer);
}else if(sum > target){
rightPointer = moveRight(nums, leftPointer, rightPointer - 1);
}else{
break;
}
}
i = moveLeft(nums, i + 1, leftPointer);
}
return res;
}
public int moveLeft(int[] nums, int left, int right){
//if left is less than right and left is less than nums.length
//also, if current number is the same as last one, continue to move
if(left < right && left < nums.length && nums[left] == nums[left - 1]){
left++;
}
return left;
}
public int moveRight(int[] nums, int left, int right){
if(right > left && right > 0 && nums[right] == nums[right + 1]){
right--;
}
return right;
}
}
复杂度分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
