三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

示例

  1. 输入：nums = [-1,0,1,2,-1,-4]
  2. 输出：[[-1,-1,2],[-1,0,1]]

解题思路

1.特殊情况的判断-数组为空或者数组长度小于3：nums == null || nums.length<=2

  1.  2.排序-因为和为0，所以满足的情况下要么都为0要么前面有负数。所以先排序进行遍历
  3.  3.外层循环寻找第一个元素-a.第一个元素后面一定会有至少两个元素<br />b.因为排序所以第一个元素一定不能大于0
  1. for(int i = 0;i<nums.length-2;i++){
  2.     if(nums[i]>0) break;
  3.     ...
  4. }
  1.      4.在外层循环里面就可以使用双指针来进行两数相加是否等于第一个元素的相反数
  1. target = -nums[i];
  2. int l = i+1,r = nums.length-1;
  3. while(l<r){
  4.     // 进行判断操作相应的++，--
  5.     // 注意：满足条件以后要左右指针都移动，不然进入循环
  6.     // 因为要去重，所以相同的值也要去掉
  7. }

最后代码

  1. class Solution {
  2.     // 因为是和为0，所以先排序找出小于0的
  3.     public List<List<Integer>> threeSum(int[] nums) {
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         if (nums == null || nums.length <= 2) return res;
  6.         // 排序
  7.         Arrays.sort(nums);
  8.         // 因为包含三个数字，所以第一个元素索引一定小于nums.length-2
  9.         for(int i = 0;i<nums.length-2;i++){ 
  10.             if (nums[i]>0) break;  // 第一个元素就大于0那和不可能为0
  11.             if (i>0 && nums[i]==nums[i-1]) continue;
  12.             // 先减去第一个元素 - 只需要判断后面两个元素相加是否等于目标值就行
  13.             target = -nums[i];
  14.             int l = i+1,r =  nums.length - 1;
  15.             while(l<r){
  16.                 if(nums[l]+nums[r]==target){
  17.                     res.add(new ArrayList<>(Arrays.asList(nums[i],nums[l],nums[r])));
  18.                     // 继续遍历满足条件的数据
  19.                     // 一定要++ -- 操作才能继续遍历
  20.                     l++;r--;
  21.                     // 答案不能重复
  22.                     while(l<r && nums[l]==nums[l-1]) l++;
  23.                     while(l<r && nums[r]==nums[r+1]) r--;
  24.                 }else if(nums[l]+nums[r]<target){
  25.                     l++;
  26.                 }else{
  27.                     r--;
  28.                 }
  29.             }
  30.         }
  31.         return res;
  32.     }
  33. }

四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/4sum

示例

  1. 输入：nums = [1,0,-1,0,-2,2], target = 0
  2. 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

思路

这题和三数之和差不多，只是需要多一层的循环。有序数组的前提下
第一层循环的时候如果当前值和上一次循环值相等那么跳过此次循环
if(i>0 && nums[i]==nums[i-1]) continue;
如果当前值和最后三个数的值加起来小于目标值也要跳过这次循环
if(target>(nums[i]+nums[len-3]+nums[len-2]+nums[len-1])) continue;
如果当前值加上后面的三个数大于目标值，那么结束循环。最小的四个数都大何况后面

第二层循环的时候开始为i+1，条件和第一次循环的条件类似
if(j>(i+1) && nums[j]==nums[j-1]) continue;
if(target>(nums[i]+nums[j]+nums[len-2]+nums[len-1])) continue;
if(target<nums[i]+nums[j]+nums[j+1]+nums[j+2]) break;

然后就开始双指针
左边开始为j+1，循环进入的条件就是left

代码

  1. class Solution {
  2.     public List<List<Integer>> fourSum(int[] nums, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         if(nums ==null || nums.length<4) return res;
  6.         // 排序
  7.         Arrays.sort(nums);
  8.         // 记录数组长度
  9.         int len = nums.length;
  10.         // 记录双指针使用到的变量
  11.         int l = 0, r=0, sum = 0;
  13.         // 1.寻找第一个数之旅
  14.         for(int i = 0;i<len-3;i++){
  15.             // 排序后的数组如果前后两个数相等则跳过此次循环（不重复四元组）
  16.             if(i>0 && nums[i]==nums[i-1]) continue;
  17.             // 如果前四个数相加都大于目标值则证明后面的相加更加大于,可以退出了
  18.             if(target<(nums[i]+nums[i+1]+nums[i+2]+nums[i+3])) break;
  19.             // 如果当前值加上后三个数个数相加都小于目标值就进入下一次循环i++
  20.             if(target>(nums[i]+nums[len-3]+nums[len-2]+nums[len-1])) continue;
  22.             // 2.开始寻找第二个数了
  23.             for(int j = i+1;j<len-2;j++){
  24.                 if(j>(i+1) && nums[j]==nums[j-1]) continue;
  25.                 if(target<nums[i]+nums[j]+nums[j+1]+nums[j+2]) break;
  26.                 if(target>(nums[i]+nums[j]+nums[len-2]+nums[len-1])) continue;
  28.                 // 3.最后两个数使用双指针寻找
  29.                 l = j+1;
  30.                 r = len-1;
  31.                 while(l<r){
  32.                     sum = nums[i]+nums[j]+nums[l]+nums[r];
  33.                     if(sum==target){
  34.                         res.add(Arrays.asList(nums[i],nums[j],nums[l],nums[r]));
  35.                         l++;r--;
  36.                         // 去重操作
  37.                         while(l<r && nums[l]==nums[l-1]) l++;
  38.                         while(l<r && nums[r]==nums[r+1]) r--;
  39.                     }else if(target>sum){
  40.                         l++;
  41.                     }else{
  42.                         r--;
  43.                     }
  44.                 }
  45.             }
  46.         }
  48.         return res;
  49.     }
  50. }