1 题目
给一个包含n个数的整数数组S，在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。
四元组(a, b, c, d)中，需要满足 a<=b<=c<=d，答案中不可以包含重复的四元组。
样例 1：
输入：
numbers = [2,7,11,15]
target = 3输出：
[]解释：2 + 7 + 11 + 15 ！= 3，不存在满足条件的四元组。
样例 2：
输入：
numbers = [1,0,-1,0,-2,2]
target = 0输出：
[[-1, 0, 0, 1],[-2, -1, 1, 2],[-2, 0, 0, 2]]解释：有3个不同的四元组满足四个数之和为0。
2 解答
排序 + 双指针
public class Solution { /** * @param numbers: Give an array * @param target: An integer * @return: Find all unique quadruplets in the array which gives the sum of zero * we will sort your return value in output */ public List<List<Integer>> fourSum(int[] numbers, int target) { // write your code here // 1、当数组为空或者元素个数小于4时，直接返回 List<List<Integer>> res = new ArrayList<>(); if (numbers == null || numbers.length <= 3) { return res; } // 2、四数之和 相对于三数之和就是固定一个 fixedNum 找三数之和为 target-fixedNum 的 // 先排序吧 Arrays.sort(numbers); // 四元组要不重复，要去重 Set<String> strSet = new HashSet<>(); // 遍历 for (int i = 0; i < numbers.length; i++) { int fixedNum = numbers[i]; // 计算差值 int minus = target - fixedNum; // 在剩下的找三数之和为 minus 的 for (int j = i+1; j < numbers.length; j++) { // 固定一个，左右指针进行移动 int num = numbers[j]; int left = j+1; int right = numbers.length-1; while (left < right) { int leftNum = numbers[left]; int rightNum = numbers[right]; int sum = num + leftNum + rightNum; // 小了，左指针++ if (sum < minus) { left++; } else if (sum > minus) { // 大了，右指针-- right--; } else { // 相等了 算一种结果 String numStr = String.format("%s%s%s%s", fixedNum, num, leftNum, rightNum); if (!strSet.contains(numStr)) { List<Integer> oneRes = new ArrayList<>(); oneRes.add(fixedNum); oneRes.add(num); oneRes.add(leftNum); oneRes.add(rightNum); res.add(oneRes); strSet.add(numStr); } // 因为数组时排序后的，所以这里向中靠拢继续找 左++ 右-- left++; right--; } } } } return res; } }
加油。