18.四数之和
自己解法
四数之和解题思路和三数之和类似，不过这个方式是固定前两个数字，后面两个数字用夹逼的方式向中间逼近，这样时间复杂度是N的3次方。在去重方面，只有在下次逻辑会重复的情况下才用去重，正常情况下相邻相等不能直接去重，因为可能会出现两个相同的数字都被选中的情况。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 4) {
return res;
}
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
for (int j = i + 1; j < nums.length - 2; j++) {
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (target > sum) {
left++;
} else if (target < sum) {
right--;
} else {
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[right] == nums[right + 1]) {
right--;
}
while (left < right && nums[left] == nums[left - 1]) {
left++;
}
}
}
while (j < nums.length - 2 && nums[j] == nums[j + 1]) {
j++;
}
}
while (i < nums.length - 3 && nums[i] == nums[i + 1]) {
i++;
}
}
return res;
}
}
官方解法
官方解法速度更快，在于利用组合的可能的最小值和最大值，规避了一些无用的判断，其它思路类似。
class Solution {
public List<List<Integer>> fourSum(int[] nums,int target){
/*定义一个返回值*/
List<List<Integer>> result=new ArrayList<>();
/*当数组为null或元素小于4个时，直接返回*/
if(nums==null||nums.length<4){
return result;
}
/*对数组进行从小到大排序*/
Arrays.sort(nums);
/*数组长度*/
int length=nums.length;
/*定义4个指针k，i，j，h k从0开始遍历，i从k+1开始遍历，留下j和h，j指向i+1，h指向数组最大值*/
for(int k=0;k<length-3;k++){
/*当k的值与前面的值相等时忽略*/
if(k>0&&nums[k]==nums[k-1]){
continue;
}
/*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/
int min1=nums[k]+nums[k+1]+nums[k+2]+nums[k+3];
if(min1>target){
break;
}
/*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
int max1=nums[k]+nums[length-1]+nums[length-2]+nums[length-3];
if(max1<target){
continue;
}
/*第二层循环i，初始值指向k+1*/
for(int i=k+1;i<length-2;i++){
/*当i的值与前面的值相等时忽略*/
if(i>k+1&&nums[i]==nums[i-1]){
continue;
}
/*定义指针j指向i+1*/
int j=i+1;
/*定义指针h指向数组末尾*/
int h=length-1;
/*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏，忽略*/
int min=nums[k]+nums[i]+nums[j]+nums[j+1];
if(min>target){
continue;
}
/*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
int max=nums[k]+nums[i]+nums[h]+nums[h-1];
if(max<target){
continue;
}
/*开始j指针和h指针的表演，计算当前和，如果等于目标值，j++并去重，h--并去重，当当前和大于目标值时h--，当当前和小于目标值时j++*/
while (j<h){
int curr=nums[k]+nums[i]+nums[j]+nums[h];
if(curr==target){
result.add(Arrays.asList(nums[k],nums[i],nums[j],nums[h]));
j++;
while(j<h&&nums[j]==nums[j-1]){
j++;
}
h--;
while(j<h&&nums[h]==nums[h+1]){
h--;
}
}else if(curr>target){
h--;
}else {
j++;
}
}
}
}
return result;
}
}
