方法2：排序加双指针
思路：在为了方便去重和减少遍历次数，我们应该保证三指针满足i<j<k的关系。i我们通过for循环固定，j和k从两头向内移动。
时间复杂度O(n^2)：数组排序O(nlogn),遍历数组O(n),双指针遍历O(n)。总体O(n^2)
空间复杂度O(1)
class Solution { public List<List<Integer>> threeSum(int[] nums) { //对数组排序 Arrays.sort(nums); int n=nums.length; List<List<Integer>> list=new ArrayList<>(); for(int i=0;i<n-2;i++){ //定一个i,移动两指针j,k,注意j是从末尾开始移动 int j=i+1; int k=n-1; while(j<k){ int count=nums[i]+nums[j]+nums[k]; //找到符合的 if(count==0){ List<Integer> arr=new ArrayList<>(); arr.add(nums[i]); arr.add(nums[j]); arr.add(nums[k]); //为了去重 if(!list.contains(arr)){ list.add(arr); } j++; k--; //加起来太大，让k--从而和变小 }else if(count>0){ k--; //加起来太小,让j++从而和变大 }else{ j++; } } } return list; } }
对上述代码可进行优化：
class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums);//排序，nums变成递增数组 List<List<Integer>> res = new ArrayList<>(); //k < nums.length - 2是为了保证后面还能存在两个数字 for(int k = 0; k < nums.length - 2; k++){ if(nums[k] > 0) break;//若nums[k]大于0，则后面的数字也是大于零（排序后是递增的） if(k > 0 && nums[k] == nums[k - 1]) continue;//nums[k]值重复了，去重 int i = k + 1, j = nums.length - 1;//定义左右指针 while(i < j){ int sum = nums[k] + nums[i] + nums[j]; if(sum < 0){ while(i < j && nums[i] == nums[++i]);//左指针前进并去重 } else if (sum > 0) { while(i < j && nums[j] == nums[--j]);//右指针后退并去重 } else { res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j]); while(i < j && nums[i] == nums[++i]);//左指针前进并去重 while(i < j && nums[j] == nums[--j]);//右指针后退并去重 } } } return res; } }
🐯5.四数之和
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
题目链接：四数之和https://leetcode-cn.com/problems/4sum/
题目思路：这道题是在三数之和的基础之上个进阶，也可以说是两数之和的进阶，只不过变成了四个数。我们不可能用4个for循环遍历，而且还得去重，肯定是会超时的。这时我们同样可以利用三数之和的性质，先将数组排序，利用四个指针i,p1,p2,j。同时保证i<p1<p2<j。每次固定i和j，判断四个下标相加的和 ，如果比target大，让p2--，如果比target小，让p1++。如果相等就放入到答案集合中。
方法: 排序加双指针
时间复杂度：O(n^3)
空间复杂度: O(logn)
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> list=new ArrayList<>(); Arrays.sort(nums); int n=nums.length; //i得保证后面还得有三个位，所以<n-3 for(int i=0;i<n-3;i++){ //得保证和i之间还有两个位，所以>i+2 for(int j=n-1;j>i+2;j--){ int x=nums[i]+nums[j]; //两指针开始的位置 int p1=i+1; int p2=j-1; while(p1<p2){ int count=x+nums[p1]+nums[p2]; if(count==target){ List<Integer> arr=new ArrayList<>(); arr.add(nums[i]); arr.add(nums[j]); arr.add(nums[p1]); arr.add(nums[p2]); //去重 if(!list.contains(arr)){ list.add(arr); } p1++; p2--; }else if(count>target){ p2--; }else{ p1++; } } } } return list; } }
🐷6.四数相加ll
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
题目链接：四数相加ll https://leetcode-cn.com/problems/4sum-ii/
题目思路：这道题其实比上一道题四数之和要简单一些，不过它却也有自己比较难处理的地方。我们不可能用四个for循环遍历，因为即使能遍历不超时，去重的步骤也是很麻烦的。其实也相当于又是两数之和的进阶。我们可以将数组两两分组，A组和B组遍历相加，将结果作为key，value当做该结果出现的次数。然后再遍历C组和D组相加的和为count，去判断map中是否有和count相加为0的key，如果有则加上该key对应的value。这样相当于进行了两次O(n^2)的遍历，总体来说还是O(n^2)的世界复杂度
方法：分组+哈希表
时间复杂度O(n^2)：两个两层for循环，总体来时间复杂度还是O(n^2)
空间复杂度O(n^2)：哈希映射需要的空间，最坏的情况下存入的值个数位n^2，也就需要O(n^2)的空间
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { Map<Integer,Integer> map=new HashMap<>(); int n=nums1.length; //用来统计答案 int anser=0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int count=nums1[i]+nums2[j]; //已存在 if(map.containsKey(count)){ //让出现的次数加1，也就是value map.put(count,map.get(count)+1); }else{ //未存在，放入map中,value为1 map.put(count,1); } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ int count2=nums3[i]+nums4[j]; //找到匹配的 if(map.containsKey(-count2)){ //加上value，也就是出现的次数 anser+=map.get(-count2); } } } return anser; } }
🍋3.刷题总结
几数之和的题目都非常的干货，深度地考察了我们算法基础能力的实践应用。特别是对哈希能力的训练，因为哈希是经典的以空间换时间，如果我们不用哈希就会超时，而且去重也非常麻烦。其次是双指针的运用，因为几数之和的题目数据大部分都在数组中，在数组中找元素大部分都离不开双指针算法。大家做完这类型的题目一定要多总结其中的规律，从二数到三数到四数，它的变化是怎样，做法又如何变化，这样才能高效刷题，早日成神！ 后续我也会出哈希专题系列以及双指针专题系列。
