2Sum，3Sum，4Sum问题（Java）_综合

【问题】知道nums[ ] ={ }和target，返回nums中能够得出target的两个元素

一、2Sum问题

1.1 nums中只有一对元素满足时

eg: 只有唯一解的情况，如：[5,3,1,6]，target=9，结果为[3,6]

import java.util.*;public class Solution {
    public static void main(String[] args){
    int[] nums = {
    5,3,1,6};int target = 9;int[] fun = fun(nums,target);System.out.print("[");System.out.print(fun[0]);System.out.print(",");System.out.print(fun[1]);System.out.println("]");}public static int[] twoSum(int[] nums,int target){
    int low = 0,high = nums.length-1;Arrays.sort(nums);int[] res = new int[2];while(low < high){
    int sum = nums[low] + nums[high];if(sum < target){
    low++;}else if(sum > target){
    high--;}else{
    res[0] = nums[low];res[1] = nums[high];return res;}}return new int[2];}
}

1.2 nums中有多对元素满足

eg:nums = [1,3,1,2,2,3]，target = 4；结果为：[[1,3],[2,2]]
在这里插入图片描述

关键点在于[1,3]和[3,1]重复

import java.util.*;public class Solution {
    public static void main(String[] args){
    int[] nums = {
    1,3,1,2,2,3};int target = 4;System.out.println(twoSum(nums,target));}public static List<List<Integer>> twoSum(int[] nums,int target){
    int low = 0;int high = nums.length-1;Arrays.sort(nums);//1 1 2 2 3 3List<List<Integer>> res = new ArrayList<>();int left = 0;int right = 0;int sum = 0;while(low < high){
    //易错点，如果放在循环外，用clear()清理list，则不可行List<Integer> list = new ArrayList<>();left = nums[low];right = nums[high];sum = left + right;if(sum < target){
    low++;}else if(sum > target){
    high--;}else if(sum == target) {
    list.add(nums[low]);list.add(nums[high]);while(low < high && nums[low] == left) low++;while(low < high && nums[high] == right) high--;res.add(list);}}return res;}
}

在这里插入图片描述

这题卡在一个地方很久，list.clear()最好别用，哪里错我也说不清楚，最后res输出的是重复的数，应该像代码中，在while循环里重新new一个ArrayList()出来。

二、3Sum问题

问是否存在三个数，a,b,c，使a+b+c=0? 要求返回不重复的三元组

看到这么长的代码先别慌，实际上就是先确定第一个数字：nums[i]，剩下的数字之和就是target - nums[i]，这个直接用twoSum()来解决，只不过它的起点l ow 要改成threeSum中的 i+1：

import java.util.*;public class Solution {
    public static void main(String[] args){
    int[] nums = {
    -1,0,1,2,-1,-4};int target = 0;System.out.println(threeSum(nums,target));}public static List<List<Integer>> threeSum(int[] nums,int target){
    List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);int len = nums.length;//穷举第一个数for(int i = 0; i < len; i++){
    //对target - nums[i]计算twoSumList<List<Integer>> lists = twoSum(nums,target-nums[i],i+1);for(List<Integer> list:lists){
    list.add(nums[i]);res.add(list);}//跳过相同数字的重复情况while(i < len-1 && nums[i] == nums[i+1]) i++;}return res;}public static List<List<Integer>> twoSum(int[] nums,int target,int start){
    //左指针改为由start开始int low = start;int high = nums.length-1;Arrays.sort(nums);//1 1 2 2 3 3List<List<Integer>> res = new ArrayList<>();int left = 0;int right = 0;int sum = 0;while(low < high){
    //易错点，如果放在循环外，用clear()清理list，则不可行List<Integer> list = new ArrayList<>();left = nums[low];right = nums[high];sum = left + right;if(sum < target){
    low++;}else if(sum > target){
    high--;}else if(sum == target) {
    list.add(nums[low]);list.add(nums[high]);while(low < high && nums[low] == left) low++;while(low < high && nums[high] == right) high--;res.add(list);}}return res;}
}

在这里插入图片描述

同理，4Sum问题，也是在3Sum的基础上加一个。

可参考文章：https://mp.weixin.qq.com/s/fSyJVvggxHq28a0SdmZm6Q