leetcode18-4Sum

本文主要是介绍leetcode18-4Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给你一个由 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个复合要求的数字，注意第一个for的剪枝

import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;public class fourSum {public static void main(String[] args) {int[] arr = {1,0,-1,0,-2,2};List<List<Integer>> res = getFour(arr,0);for(List<Integer> lis : res) {for(Integer data : lis) {System.out.print(data + " ");}System.out.println();}}public static List<List<Integer>> getFour(int[] arr,int target) {int len = arr.length;Arrays.sort(arr);Set<List<Integer>> set = new HashSet();for(int i = 0;i<len-3;i++) {if(i > 0 && arr[i] == arr[i-1]) {continue;}for(int j = i+1;j<len-2;j++) {int m = j+1;int n = len - 1;while(m<n) {int data = arr[i]+arr[j]+arr[m]+arr[n];if(data == target) {List<Integer> lis = new ArrayList();lis.add(arr[i]);lis.add(arr[j]);lis.add(arr[m]);lis.add(arr[n]);set.add(lis);m++;n--;} else if(data < target) {m++;} else {n--;}}}}List<List<Integer>> res = new ArrayList();res.addAll(set);return res;}
}

这篇关于leetcode18-4Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---