题目: 四数之和

来自智得网
跳转至： 导航、​ 搜索

分析

四数之和明显和两数之和、三数之和是类似的题目，所以可以用同样的方式进行求解。可以用暴力破解、双指针、Hash法等方式进行求解。

暴力破解

因为是求解四数之和，所以暴力破解法需要四层循环，四层循环可以遍历出来集合中所有的四元组，然后计算所有四元组的和，因为答案是需要返回所有符合结果的四元组，所以如果四元组的和为目标值，则存储这个四元组。

使用了四层循环，所以暴力破解法的时间复杂度是Θ（n4）。

因为题目要求返回不重复的值，所以需要对结果进行去重。

去重可以通过比对所有符合结果的四元组的值来进行去重，但是常规的去重需要两两比对来判断是否重复，两两比对过程时间复杂度也是Θ（n2）。

去重可以通过Hash表的方式进行去重，四元组可以通过排序来确定唯一的序列，将排序之后的序列存储在Hash表。当有新的四元组符合条件的时候判断该值是否已经存在来进行去重，通过Hash表的方式去重，每个结果只需要判读一次，所以时间复杂度是Θ（n）。

双指针

首先将数组排序。

因为是四数之和，所以先使用两层循环组合两个数字，假如两个数字的和是m，然后求解数组中其余的位置是否存在两个数字的和等于目标值减去m，假如该结果为n，就可以使用双指针的方式来求解，定义两个指针分别指向数组的头尾部。计算头尾指针指向的两个数字的和是否等于n，如果相等则求得一组四元组的解，如果该值大于n，则将尾部指针左移，否则将头部指针右移。

因为是求数组中所有符合条件的值，所以求的一组解之后，仍然需要继续移动指针，直到左右指针发生重合位置。

因为双指针法过程中四元组是已经排序的，所以去重的过程可以使用Hash表的方式进行。

双指针过程中排序的时间复杂度是Θ（n*lg（n）），计算四数之和的时间复杂度是Θ（n3），所以整体的时间复杂度是Θ（n3）。

Hash法

四数之和可以转换为两数之和，所以先使用两层循环组合两个数字，假如两个数字的和是m，然后求解数组中其余的位置是否存在两个数字的和等于目标值减去m，假如该结果为n，就可以使用Hash法来求解问题，问题就转换为了查找剩余集合中是否存在两数之和是n的问题。因为两数之和的时间复杂度是O（n），四数之和还有两层循环，所以时间复杂度是O（n3）。

解题

暴力破解

代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class DoublePointSolution {

    public static List<List<Integer>> solute(List<Integer> nums, int target){
        List<List<Integer>> result = new ArrayList<>();

        Collections.sort(nums, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for(int i = 0; i < nums.size() - 4; i ++){
            int firstNum = nums.get(i);
            if(firstNum > target){
                break;
            }
            if (i > 0 && nums.get(i) == nums.get(i - 1)) {
                continue;
            }
            for(int j = i + 1; j < nums.size() - 3; j ++){
                int secondNum = nums.get(j);
                if(firstNum + secondNum > target){
                    break;
                }
                if (j > i + 1 && nums.get(j) == nums.get(j - 1)) {
                    continue;
                }

                int firstPoint = j + 1;
                int secondPoint = nums.size() - 1;
                while(true){
                    if(firstPoint >= secondPoint){
                        break;
                    }

                    int thirdNum = nums.get(firstPoint);
                    int fourthNum = nums.get(secondPoint);
                    if(firstNum + secondNum + thirdNum + fourthNum == target){
                        result.add(List.of(firstNum, secondNum, thirdNum, fourthNum));
                        break;
                    }else if(firstNum + secondNum + thirdNum + fourthNum > target){
                        secondPoint--;
                    }else{
                        firstPoint++;
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args){
        List<Integer> nums = new ArrayList<>(List.of(1, 0, -1, 0, -2, 2));
        List<List<Integer>> result = solute(nums, 0);

        result.stream().forEach(
                item-> {
                    System.out.println(item.stream().map(String::valueOf).collect(Collectors.joining(",")));
                }
        );
    }

}

双指针

此类问题使用双指针求解的时候，需要先把数组进行排序，之后把其中两个数字进行组合，剩下的两个数字用双指针的方式求解。

一个指针指向两个组合数字中较大那个的下一位，另一个指针指向数组的末尾。

然后计算两个组合数字加上两个指针指向位置的四个数字的和，

如果和超过了目标值，则右置针左移；

如果和比目标值小，则左置针右移；

用双指针的方式可以把算法的时间复杂度减少一个量级，把O（n4）变为O（n3）。

代码如下：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class DoublePointSolution {

    public static List<List<Integer>> solute(List<Integer> nums, int target){
        List<List<Integer>> result = new ArrayList<>();

        Collections.sort(nums, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for(int i = 0; i < nums.size() - 4; i ++){
            int firstNum = nums.get(i);
            if(firstNum > target){
                break;
            }
            if (i > 0 && nums.get(i) == nums.get(i - 1)) {
                continue;
            }
            for(int j = i + 1; j < nums.size() - 3; j ++){
                int secondNum = nums.get(j);
                if(firstNum + secondNum > target){
                    break;
                }
                if (j > i + 1 && nums.get(j) == nums.get(j - 1)) {
                    continue;
                }

                int firstPoint = j + 1;
                int secondPoint = nums.size() - 1;
                while(true){
                    if(firstPoint >= secondPoint){
                        break;
                    }

                    int thirdNum = nums.get(firstPoint);
                    int fourthNum = nums.get(secondPoint);
                    if(firstNum + secondNum + thirdNum + fourthNum == target){
                        result.add(List.of(firstNum, secondNum, thirdNum, fourthNum));
                        break;
                    }else if(firstNum + secondNum + thirdNum + fourthNum > target){
                        secondPoint--;
                    }else{
                        firstPoint++;
                    }
                }
            }
        }

        return result;
    }

    public static void main(String[] args){
        List<Integer> nums = new ArrayList<>(List.of(1, 0, -1, 0, -2, 2));
        List<List<Integer>> result = solute(nums, 0);

        result.stream().forEach(
                item-> {
                    System.out.println(item.stream().map(String::valueOf).collect(Collectors.joining(",")));
                }
        );
    }

}
取自“https://www.aigetting.com/index.php?title=题目:四数之和&oldid=2023”