題目鏈接 | 文檔講解 |視頻講解 :?鏈接

?1.思路：

• 0.定義一個count，計算最終出現的次數

• 1.先遍歷nums1和nums2,求出兩者的和，map的key是和，value是出現的次數

• 2.再遍歷nums3和nums4，求出0-兩者的和

• 3.判斷map集合中是否出現 0-兩者的和,出現過count+map的value值，否則為count+0

【注】不能是count++,因為在記錄nums1和nums2，[1,2] [2,1] key=3的出現過2次，value存的是2，count+的是value值

?2.代碼：

 public  int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int count=0;Map<Integer,Integer> map=new HashMap<>();//key是 nums1[i]+nums[j]的值  value是出現的次數for (int a : nums1) {for (int b : nums2) {
//                if(map.containsKey(a+b)){
//                    map.put(a+b,map.get(a+b)+1);
//                }else {
//                    map.put(a+b,1);
//                }//使用map.getOrDefault()方法，無需在if判斷，不存在,value為默認值0，存在則獲取對應的值map.put(a+b,map.getOrDefault(a+b,0)+1);}}for (int c : nums3) {for (int d : nums4) {
//                if(map.containsKey(0-c-d)){
//                    count+=map.get(0-c-d);
//                }count+=map.getOrDefault(0-c-d,0);}}return count;}

15. 三數之和

題目鏈接 | 文檔講解 |視頻講解：鏈接

?1.思路：

• 1.先排序，第一個元素>0,直接返回空集合

• 2.使用for循環+雙指針, 初始時左指針指向第二個元素，右指針指向最后一個元素

• 3.去重操作,for循環的當前元素和上一個元素相等，continue eg: -1 -1 0 1 避免出現重復的三元數組 2個[-1 0 1]

• 4.循環判斷條件，左右指針不能相等，因為求是3個元素相加和，相等成了2個元素的和，判斷三數之和num ,num>0,right--, num<0,left++ , num==0,收集三元數組，left++ right--? ? ? ??【注】==0時，去重判斷，left和left-1是否相等，right和right+1是否相等，避免出現 -1 0 0 1 1 ，2個[-1 0 1]

?2.代碼：

 public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result=new ArrayList();//1.排序Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {//第一個元素大于0,就不會出現和為0的數組了if(nums[i]>0){return result;}//三元數組不能重復,eg: -1 -1 0 1// 第一次循環 i指向第一個-1，得出了三元數組[-1 0 1]// 第二次循環  i指向第二個-1,再次得出了三元數組[-1 0 1],與題目要求不符，所以在這里要進行去重判斷//為什么不是和其下一個元素進行比較，而是和當前元素的前一個比較呢？if(i>0 && nums[i]==nums[i-1]){continue;}int left=i+1;int right=nums.length-1;while (left<right){int num=nums[i]+nums[left]+nums[right];//num>0,說明right需要變小if(num>0){right--;}//num>0,說明left需要變大if(num<0){left++;}if(num==0){List<Integer> list=new ArrayList<>();list.add(nums[i]);list.add(nums[left]);list.add(nums[right]);result.add(list);left++;right--;//因為left在上面已經+1,,所以需要與其前一個元素進行比較//避免出現-2 0 0 1 2 2  避免出現2個 [-2,0,2]while (left<right && nums[left]==nums[left-1]){left++;}//因為right在上面已經-1,所以需要與其后面一個元素進行比較while (left<right && nums[right]==nums[right+1]){right--;}}}}return  result;}

題目鏈接 | 文檔講解 |視頻講解：鏈接

?1.思路：

• ?排序?

• 2層for循環+雙指針

• ?第一層for循環：判斷nums[i]>0 && nums[i]>target,返回空集合。必須判斷nums[i]>0,因為如果是負數，會出現 [-5,-1 ,0 ,0] target= -6 ，判斷當前元素和其上一個元素是否相等，相等，continue,退出本次循環

• 第二層for循環：nums[i]+nums[j]>0 && nums[i]+nums[j]>target，break,退到上一層循環，避免出現 [-5,-1 ,0 ,1] target=-7 ，?判斷當前元素和其上一個元素是否相等，相等，continue,退出本次循環

• ?while循環，左右指針的移動柜規則同三數之和，在這里不做贅述

?2.代碼：

 public  List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result =new ArrayList<>();//1.排序Arrays.sort(nums);//2層for循環+雙指針for (int i = 0; i < nums.length; i++) {// 【注】：不能直接判斷nums[i]>target 避免出現 [-5,-1 ,0 ,0]  target= -6  -5>-6但是會出現符合條件的四元數組,//數組中存在負數，是有可能會越加越小的if(nums[i]>0 && nums[i]>target){return  result;}//一級去重if(i>0 && nums[i]==nums[i-1]){continue;}for (int j = i+1; j < nums.length; j++) {// 【注】：不能直接判斷nums[i]+nums[j]>target,避免出現 [-5,-1 ,0 ,1]  target=-7  -5+(-1)>-7 但是會出現符合條件的四元數組if(nums[i]+nums[j]>0 && nums[i]+nums[j]>target){break;}//二級去重if(j>i+1 && nums[j]==nums[j-1]){continue;}int left=j+1;int right=nums.length-1;//下面同三元數組之和while (left<right){int num=nums[i]+nums[j]+nums[left]+nums[right];if(num>target){right--;}if(num<target){left++;}if(num==target){List<Integer> list=new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[left]);list.add(nums[right]);result.add(list);left++;right--;while (left<right && nums[left]==nums[left-1]){left++;}while (left<right && nums[right]==nums[right+1]){right--;}}}}}return  result;}