Three_Sum问题

三数求和为0，返回动态数组问题

输入：一个数组
输出：相加为0的三个元素组成的 ArrayList<Integer>
要求：输出不能还有重复
用例：[-1, 0, 1, 2, -1, -4] ====> [ [-1, 0, 1], [-1, -1, 2] ]

分析

这个很简单想到穷举法，O(n^3)。三重循环即可以做。至于重复的部分可以用 HashSet 来处理(相当于python中的set)。但是提交，Runtime Error。

思路

排序双指针法

这种方法不能穷举所有可能的三个数的组合，是有目的 移动（知道下一个向大/小方向移动），会逼近给定的和。

将 3Sum 问题看做是 扩展的 2Sum 问题。
首先，要做的是将给定数组排序，用到 Arrays.sort() 方法。
之后，将第一个数字给定，用两个指针遍历后面的数字，和为0时，同时移动两个指针；否则，只移动一个。（因为已经排序了）
最后，先写到 hs 中缓存来去重。

排序nlog(n)，循环n^2，整体时间复杂度为 O(n^2)

代码

package day_3;
import java.util.*;
// 给定一个数组，返回加和为0 的三个元素列表
// 穷举法   --- O（n^3） 这个 TLE了
// 双指针法 --- O(n^2)
public class ThreeSums {
    public List<List<Integer>> threeSum(int[] nums){
        int count = nums.length;
        List<List<Integer>> list = new ArrayList<List<Integer>>(); 
        if(count<3 || nums == null){
            System.out.println("无效输入");
            return list;
        }
        Arrays.sort(nums);
        
        // 用作去重的 hs
        HashSet<ArrayList<Integer>> hs = new HashSet<ArrayList<Integer>>();
        for(int i=0;i<count-2;i++){
            int low = i+1;
            int high = count-1;  // 两个指针
            while(low<high){
            int sum = nums[i]+nums[low]+nums[high];
            if(sum == 0){
                ArrayList<Integer> aList = new ArrayList<Integer>();
                aList.add(nums[i]);
                aList.add(nums[low]);
                aList.add(nums[high]);
                if(!hs.contains(aList)){
                    hs.add(aList);
                    list.add(aList);
                }
                low++;
                high--;
            }
            else if(sum < 0)
            low++;
                else 
                high--;
            }
        }
        return list;
    }
    
public static void main(String args[]){
    int a[] = {0,0,0};
    ThreeSums t = new ThreeSums();
    System.out.println(t.threeSum(a));
    }   
}

4Sum问题

对于4Sum问题，我们也可以按照这个思路来解答，不过多加一个元素，还是双指针。
具体代码要自己调整一下。

其实还有一个思路，对于 kSum 的拓展问题，通过回溯法来实现。
参考别人的代码。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) return new ArrayList<>();
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        helper(nums, target, res, ans, 0, 4);  // 如果你想五数之和，将这里的4改成5即可，另外上面的判断条件也需要改一下，依次类推.....6 sum 7 sum .... 都可以解决。
        return res;
    }
    private void helper(int[] nums, int target, List<List<Integer>> res, List<Integer> ans, int cur, int kSum) {
        if (target < kSum * nums[cur] || target > kSum * nums[nums.length - 1]) return ;  // 不可能存在相应的kSum数组
        if (kSum == 2) help2Sum(nums, target, res, ans, cur);
        else {
            for (int i = cur, len = nums.length; i <= len - kSum; i++) {
                if (i > cur && nums[i - 1] == nums[i]) continue;  // 去重
                ans.add(nums[i]);
                helper(nums, target - nums[i], res, ans, i + 1, kSum - 1);  // 回溯
                ans.remove(ans.size() - 1);
            }
        }
    }
    private void help2Sum (int[] nums, int target, List<List<Integer>> res, List<Integer> ans, int cur) {
        int lo = cur;
        int hi = nums.length - 1;
        while (lo < hi) {
            int sum = nums[lo] + nums[hi];
            if (sum < target) {
                lo++;
            } else if (sum > target) {
                hi--;
            } else {
                ans.add(nums[lo]); ans.add(nums[hi]);
                res.add(new ArrayList<Integer>(ans));
                ans.remove(ans.size() - 1); ans.remove(ans.size() - 1);
                while (lo < hi && nums[lo + 1] == nums[lo++]) ;
                while (lo < hi && nums[hi - 1] == nums[hi--]) ;
            }
        }
    }
}

作者：clthinking-2
链接：https://leetcode-cn.com/problems/4sum/solution/java-4ms-ji-bai-liao-100-ke-kuo-zhan-zi-ksumzhi-he/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。