Leet Code 18.四数之和

给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素a,b,c和d，适合a+b+c+d的值与target相等？找出所有满足条件且不重复的四元组。

与三数之和一样的思路。前两个数两个循环，后两个数用指针遍历的方式。在整体循环框架、指针遍历码好后，要添加条件来增加遍历速度，以及去重。

• 如果输入数组不满4个，则可以直接返回空字符串
• 在i循环时，可以判断是否nums[i]和nums[i-1]相等，相等就可以跳过，因为这种情况遍历过
• 在i循环时，也可以判断是否最小的四个数之和已经大于target，如果大于，说明后面更不可能满足，可以直接结束循环，返回结果
• 同理，在j循环，也要判断是否存在nums[j]和nums[j-1]相等的情况
• 在指针遍历的适合，也要判断是否L和R指针下各自与附近的数相等

提交代码

import java.util.*;
import static java.lang.Math.min;

public class leetcode {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String str = scan.nextLine();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = scan.nextInt();
        }
        int target = scan.nextInt();
        List result = fourSum(nums, target);
        System.out.println(result);
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;
        if(nums == null || len < 4) return ans;
        Arrays.sort(nums);
        for(int i = 0; i<len-3 ; i++) {
            if( i>0 && nums[i] == nums[i-1]) continue;
            if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
            for(int j = i+1; j<len-2; j++) {
                if( j>i+1 && nums[j] == nums[j-1]) continue;
                int L = j + 1;
                int R = len - 1;
                while(L < R) {
                    int sum = nums[i] + nums[j] + nums[L] + nums[R];
                    if(sum == target) {
                        ans.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
                        while (L < R && nums[L] == nums[L+1]) L++;
                        while (L < R && nums[R] == nums[R-1]) R--;
                        L++;
                        R--;
                    }
                    else if (sum - target < 0) L++;
                    else if (sum - target > 0) R--;
                }
            }
        }
        return ans;
    }
}

Leet Code 18.四数之和

原文：https://www.cnblogs.com/chenshaowei/p/12641326.html