寒光博客

[LeetCode]18. 四数之和
题目 给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a...
扫描右侧二维码阅读全文
23
2020/06

[LeetCode]18. 四数之和

题目

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

注意:

答案中不可以包含重复的四元组。

示例:

 给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Related Topics 数组 哈希表 双指针

分析及反思

和 sum3 一样 但是其中的去重我wa了四次,,所以直接暴力去重,做了HashSet
去重的问题在 j上
不去重 [-3,-2,-1,0,0,1,2,3] wa,多出一个一样的组
去重0000 wa
..暴力打法好,等我内功深厚之后再来高效率ac

代码

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        HashSet<List<Integer>> set = new HashSet<>();

        if (nums == null || nums.length < 4) {//特判
            return ans;
        }
        Arrays.sort(nums);//排序
        for (int i = 0; i < nums.length - 3; i++) {
//            if (nums[i] > target) break; //大于目标数
//            if (i > 0 && nums[i] == nums[i - 1]) continue;//i去重

            for (int j = i + 1; j < nums.length; j++) {
//                if (nums[i] + nums[j] > target) break;
//                if (j > i && nums[j] == nums[j - 1]) continue;//j去重
                int l = j + 1, r = nums.length - 1;

                while (l < r) {
                    int sum = nums[i] + nums[j] + nums[l] + nums[r];
                    if (sum > target) r--;//太大了 大的减少
                    else if (sum < target) l++;
                    else {
                        set.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--;
                    }
                }
            }
        }
        ans.addAll(set);
        return ans;
    }
}
本文作者:Author:     文章标题:[LeetCode]18. 四数之和
本文地址:http://dxoca.cn/Algorithm/367.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:June 23rd, 2020 at 05:57 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

2 comments

  1. 尹苏宽 Google Chrome 83.0.4103.106 Windows 10 中国 江西 新余

    这道题我一直留着没做,我想着什么时候我的回溯,能剪枝剪到这道题通过

    1. 寒光博客 Google Chrome 81.0.4044.138 Windows 10 中国 青海 西宁
      @尹苏宽

      我也做不到 剪枝.... 害 暴力set去重