四数之和
题目形容：给定一个蕴含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不反复的四元组。
留神：答案中不能够蕴含反复的四元组。
示例阐明请见LeetCode官网。
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
解法一：双指针法
首先，将nums排序；而后first和fourth指针别离从数组的第一个和最初一位开始，second和third指针别离从first+1和fourth-1处从两边向内挪动，直到second不小于third，挪动过程中须要判断4个指针所指向的数字之和是否和target相等，如果相等，则放到后果集result外面。 直到遍历到first不小于fourth-2为止，最初返回后果result。
import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Solution { public static List<List<Integer>> fourSum(int[] nums, int target) { if (nums == null || nums.length < 4) { return new ArrayList<>(); } if (nums.length == 4 && nums[0] + nums[1] + nums[2] + nums[3] != target) { return new ArrayList<>(); } Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); for (int first = 0, fourth = nums.length - 1; first < fourth - 2; first++) { // 过滤掉反复的 if (first > 0 && nums[first] == nums[first - 1]) { continue; } while (first < fourth - 2) { // 过滤掉反复的 if (fourth < nums.length - 1 && nums[fourth] == nums[fourth + 1]) { fourth--; continue; } for (int second = first + 1, third = fourth - 1; second < third; second++) { // 过滤掉反复的 if (second > first + 1 && nums[second] == nums[second - 1]) { continue; } while (second < third && nums[first] + nums[second] + nums[third] + nums[fourth] > target) { third--; } if (second != third && nums[first] + nums[second] + nums[third] + nums[fourth] == target) { result.add(new ArrayList<>(Arrays.asList(new Integer[]{nums[first], nums[second], nums[third], nums[fourth]}))); } } fourth--; } fourth = nums.length - 1; } return result; } public static void main(String[] args) { int[] nums = new int[]{-3, -1, 0, 2, 4, 5}; for (List<Integer> integers : fourSum(nums, 0)) { for (Integer integer : integers) { System.out.print(integer + "/"); } System.out.println(); } }}【每日寄语】忠诚的守住本人最后的幻想，让生存的每一天都变得有意义。