15. 三数之和&&18. 四数之和

15. 三数之和

思路：指针+排序

class Solution { public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans = new ArrayList(); int len = nums.length; if(nums == null || len < 3) return ans; Arrays.sort(nums); // 排序 for (int i = 0; i < len ; i++) { if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i+1; int R = len-1; while(L < R){ int sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ ans.add(Arrays.asList(nums[i],nums[L],nums[R])); while (L<R && nums[L] == nums[L+1]) L++; // 去重 while (L<R && nums[R] == nums[R-1]) R--; // 去重 L++; R--; } else if (sum < 0) L++; else if (sum > 0) R--; } } return ans; } }

18. 四数之和

使用四个指针(i<j<L<R)。固定最小的I和J在左边，L=J+1,R=_size-1 移动两个指针包夹求解。 保存使得nums[i]+nums[j]+nums[L]+nums[R]==target的解。偏大时R左移，偏小时L右移。L和R相 遇时，表示以当前的i和j为最小值的解已经全部求得。j++,进入下一轮循环j循环，当j循环结束后。 i++，进入下一轮i循环。 即(i在最外层循环，里面嵌套j循环，再嵌套双指L,R包夹求解)

class Solution{ public List<List<Integer>> fourSum(int[] nums,int target){ List<List<Integer>> ans=new ArrayList<>(); if(nums==null||nums.length<4) return ans; Arrays.sort(nums); int length=nums.length; /*定义4个指针i，j，L，R i从0开始遍历，j从i+1开始遍历，留下L和R，L指向j+1，r指向数组最大值*/ for(int i=0;i<length-3;i++){ if(i>0&&nums[i]==nums[i-1]){ continue; } /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/ int min1=nums[i]+nums[i+1]+nums[i+2]+nums[i+3]; if(min1>target){ break; } /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/ int max1=nums[i]+nums[length-1]+nums[length-2]+nums[length-3]; if(max1<target){ continue; } /*第二层循环j，初始值指向i+1*/ for(int j=i+1;j<length-2;j++){ /*当j的值与前面的值相等时忽略*/ if(j>i+1&&nums[j]==nums[j-1]){ continue; } /*定义指针L指向j+1*/ int L=j+1; /*定义指针R指向数组末尾*/ int R=length-1; /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/ int min=nums[i]+nums[j]+nums[L]+nums[L+1]; if(min>target){ break; } /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/ int max=nums[i]+nums[j]+nums[R]+nums[R-1]; if(max<target){ continue; } /*计算当前和，如果等于目标值，L++并去重，R--并去重，当当前和大于目标值时R--，当当前和小于目标值时L++*/ while (L<R){ int curr=nums[i]+nums[j]+nums[L]+nums[R]; if(curr==target){ ans.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R])); while(L<R&&nums[L]==nums[L+1]) L++; while(L<R&&i<R&&nums[R]==nums[R-1]) R--; L++; R--; } else if(curr>target) R--; else L++; } } } return ans; } }