Loading...
首页 计算机 算法 算法题 中等

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a 、 b 、 c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

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

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

题解

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 排序
        Arrays.sort(nums);
        // 存储所有结果
        Set<List<Integer>> result = new HashSet<>();
        // 存储每一组结果
        List<Integer> temp = new ArrayList<>();
        // 递归
        recursion(nums, target, result, temp, 0, 3);
        return new ArrayList<>(result);
    }
    /***
     * 循环递归
     *
     * @param nums
     * @param target 目标值
     * @param result 所有结果
     * @param temp 一个结果
     * @param i 下标
     * @param total 还剩几个数
     */
    private void recursion(int[] nums, long target, Set<List<Integer>> result, List<Integer> temp, int i, int total){
        // 循环
        for (int index = i; index < nums.length - total; index++) {
            // 剪枝，当目标值小于 0 并且当前值大于 0 时，后面也不会满足要求
            if (target < 0 && nums[index] > 0) break;
            // 当达到 3 个数时并且减掉下一个数为 0 时，存储结果
            if (total == 0 && target - nums[index] == 0) {
                // 添加第四个数
                temp.add(nums[index]);
                // 拷贝一份存储
                List<Integer> newTemp = new ArrayList<>(temp);
                result.add(newTemp);
                // 移除最后一个数
                temp.remove(temp.size() - 1);
                // 剪枝，因为排过序，所以后面的都将不满足要求，跳出循环
                break;
            }else if (total == 0 && target - nums[index] < 0){
                // 剪枝，当达到 3 个数时，并且减掉最后一个数小于 0 时，说明后面也不满足要求，跳出循环
                break;
            } else if (total == 0) {
                // 当达到 3 个数时，并且不满足上面要求，进行下次循环
                continue;
            }
            // 存储当前数
            temp.add(nums[index]);
            // 进行递归
            recursion(nums, target - nums[index], result, temp, index + 1, total - 1);
            // 移除最后一个添加进来的数
            temp.remove(temp.size() - 1);
        }
    }
}