算法训练营第十四天 | 18. 四数之和

给你一个由n个整数组成的数组nums和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]若两个四元组元素一一对应则认为两个四元组重复0 a, b, c, d na、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 109public ListListInteger fourSum(int[] nums, int target) { Arrays.sort(nums); return nSumTarget(nums, 4, 0, (long) target); } public ListListInteger nSumTarget(int[] nums, int n, int start, long target) { ListListInteger res new ArrayList(); int numsLength nums.length; //n不能小于2或者数组长度不能小于n if (n 2 || numsLength n) { return res; } //两数和的问题使用双指针 if (n 2) { int left start, right numsLength - 1; while (left right) { int num1 nums[left], num2 nums[right]; long sum num1 num2; if (sum target) { res.add(new ArrayList(Arrays.asList(num1, num2))); while (left right num1 nums[left]) { left; } while (left right num2 nums[right]) { right--; } } else if (sum target) { while (left right num1 nums[left]) { left; } } else { while (left right num2 nums[right]) { right--; } } } } else { //n数之和的问题递归处理 for (int i start; i numsLength; i) { int baseNum nums[i]; ListListInteger nSumTarget nSumTarget(nums, n - 1, i 1, target - baseNum); for (ListInteger list : nSumTarget) { list.add(baseNum); res.add(list); } while (i numsLength - 1 nums[i] nums[i 1]) { i; } } } return res; }