三数之和
点击查看代码
class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums); int n = nums.length;List<List<Integer>> res = new ArrayList<>();//优化1：如果第一个大于0，直接终结if(nums[0] > 0){return res;}for(int i = 0 ; i < n - 2 ; i++){int x = nums[i];if(i != 0 && nums[i] == nums[i-1]){continue;}//优化2:如果前面三个加起来大于0，直接breakif(x + nums[i] + nums[i+1] >0){break;}//优化3：如果x加上最后两个数小于0，直接continueif(x + nums[n-1] + nums[n-2] < 0){continue;}int l = i + 1;int r = n - 1;while(l < r){int sum = x + nums[l] + nums[r];if(sum == 0){res.add(new ArrayList<>(Arrays.asList(x, nums[l],nums[r])));l++;while(l < r && nums[l] == nums[l-1]){l++;}r--;while(l < r && nums[r] == nums[r+1]){r--;}}else if(sum < 0){l++;}else{r--;}}}return res;}
}
最接近的三数之和
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int diff = Integer.MAX_VALUE;
int res = 0;
for(int i = 0 ; i < n - 2; i++){
int x = nums[i];
if(i != 0 && nums[i] == nums[i-1]){
continue;
}
//优化1：如果有三个数大于target，直接break.后面无论怎么选和都不会比这个s还小
int s = x + nums[i+1] + nums[i+2];
if(s > target){
if(s-target < diff){
res = s;
}
break;
}
//优化2：x加上后面任意两个数都不超过target，直接continue，不需要跑双指针了.
s = x + nums[n-2] + nums[n-1];
if(s < target){
if(target-s < diff){
diff = target - s;
res = s;
}
continue;
}
int l = i+1;
int r = n-1;
while(l < r){
int sum = x + nums[l] + nums[r];
if(sum == target){
return sum;
}
if(sum - target >0){
if(sum - target < diff){
diff = sum - target;
res = sum;
}
r--;
while(l < r && nums[r] == nums[r+1]){
r--;
}
}
else{
if(target - sum < diff){
diff = target - sum;
res = sum;
}
l++;
while(l < r && nums[l] == nums[l-1]){
l++;
}
}
}
}
return res;
}
}