【LeeCode】18. 四数之和

【题目描述】

给你一个由 ​​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​​

你可以按 任意顺序 返回答案 。

​​​​https://leetcode.cn/problems/4sum/​​

【示例】

【代码】​​韦溜溜​​

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int i,left ,right;
        long sum;
        Set<String> set = new HashSet<>();
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for (int k = 0; k < nums.length ; k++) {
            for (i = k + 1; i < nums.length; i++) {
                left = i+1;
                right = nums.length - 1;
                while (left < right){
                    sum = (long)nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum == target){
                        List<Integer> integerList =
                                Arrays.asList(nums[k], nums[i], nums[left], nums[right]);
                        String key = integerList.toString();
                        if(!set.contains(key)){
                            set.add(key);
                            lists.add(integerList);
                        }
                        right--;
                        left++;
                        //找到了还得接着移动
                    } else if (sum > target ) {
                        right--;
                    } else {
                        left++;
                    }
                }
            }
        }
        return lists;
    }
}

【代码】admin

通过率：281 / 292  需要注意的是因为第一次获取到list集合后, break退出了 需要继续判断 start++/end--

思路参考 ​​【LeeCode】16. 最接近的三数之和  ​​

基于排序 + 双指针，区别的是这里是四个数字, 所以用了3层循环, i,j为基础, start和end循环遍历 

package com.company;

import java.util.*;

// 2022-02-07   
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int start = j + 1;
                int end = nums.length - 1;
                if (start > end) break;
                LinkedList<Integer> list = new LinkedList<>();
                int sum = 0;
                while (start < end) {
                    // System.out.println(nums[i] + ": " +  nums[j] + ": " + + nums[start] + ": " + nums[end]);
                    sum = nums[i] + nums[j] + nums[start] + nums[end];
                    if (sum == target) {
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[start]);
                        list.add(nums[end]);
                        if (!res.contains(list) && list.size() == 4) {
                            res.add(list);
                            list = new LinkedList<>();
                        }
                        // 注意： 这里是需要继续判断的，不能直接break
                        start++;
                        end--;
                    } else if (sum > target) {
                        end--;
                    } else {
                        start++;
                    }
                }
            }
        }
        System.out.println(res);
        return res;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);  // 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
        new Solution().fourSum(new int[]{2,2,2,2,2}, 8);  // 输出：[[2,2,2,2]]
    }
}

第二版本: 通过率 291/292  最后2个版本超时了

package com.company;

import java.util.*;

// 2022-02-07
class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int start = j + 1;
                int end = nums.length - 1;
                if (start > end) break;
                long sum = 0;
                while (start < end) {
                    sum = nums[i] + nums[j] + nums[start] + nums[end];
                    if (sum == target) {
                        List<Integer> list = Arrays.asList(nums[i], nums[j], nums[start], nums[end]);
                        if (!res.contains(list)) {
                            res.add(list);
                        }
                        start++;
                        end--;
                    } else if (sum > target) {
                        end--;
                    } else {
                        start++;
                    }
                }
            }
        }
        System.out.println(res);
        return res;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0);  // 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
        new Solution().fourSum(new int[]{2,2,2,2,2}, 8);  // 输出：[[2,2,2,2]]
    }
}