【萌新解题】四数之和
作者：面试官问
- 2022 年 7 月 17 日
本文字数：4431 字
阅读完需：约 15 分钟
关于我：微信公众号：面试官问，原创高质量面试题，始于面试题，但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目，本题是力扣第 18 题：四数之和：https://leetcode.cn/problems/4sum/。
题目描述
给你一个由 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
你可以按 任意顺序 返回答案 。
解题说明
四数之和其实解法和三数之和非常类似，我们直接参考【萌新解题】三数之和中的解法，可以很快依法炮制出如下代码：
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { // 数组排序 Arrays.sort(nums); // 数组长度 int len = nums.length;
// 结果集合 List<List<Integer>> ans = new ArrayList<>(); List<Integer> tmp = null;
for (int i=0; i<len; ++i) { // 固定nums[i] List<List<Integer>> res = threeSum(nums, i+1, target - nums[i]); for (List<Integer> item : res) { item.add(nums[i]); ans.add(item); }
// 跳过重复元素 while (i < len-1 && nums[i] == nums[i+1]) { ++i; } } return ans; }
/** * 三数之和，输入数组已经排好序 * 在数组nums中找出所有和等于target的不重复三元组 */ public List<List<Integer>> threeSum(int[] nums, int start, int target) { // 数组长度 int len = nums.length;
// 结果集合 List<List<Integer>> ans = new ArrayList<>(); // 结果集合中的某一个三元组 List<List<Integer>> tmp = null;
for (int i = start; i < len; ++i) { // 固定nums[i]作为第一个元素，通过twoSum得到所有满足条件的另外两个元素 // 然后一起组成一个三元组，注意，twoSum 入参中，数组开始的下标start要设置 // 为i+1，不能再包含 nums[i] tmp = twoSum(nums, i + 1, target - nums[i]); for (List<Integer> item : tmp) { item.add(nums[i]); // 找到符合条件的一个三元组，并添加到结果结合中 ans.add(item); }
// 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 while (i < len - 1 && nums[i] == nums[i + 1]) { ++i; } } return ans; }
/** * 两数之和 * 输入数组nums已经排好序，无需重复排序，且下标从start开始 * 也就是找出从start开始到nums.length之间，所有满足和为target的不重复二元组 */ public List<List<Integer>> twoSum(int[] nums, int start, int target) { // 数组长度 int len = nums.length;
// 左指针，指向数组开头 int left = start;
// 右指针，指向数组尾部 int right = len - 1;
// 返回结果 List<List<Integer>> ans = new ArrayList<>();
// 开始循环 while (left < right) { int sum = nums[left] + nums[right];
// 保存当前循环的第一个数，后面用于判重 int numLeft = nums[left];
// 保存当前循环的第二个数，后面用于判重 int numRight = nums[right];
if (target == sum) { // 找到目标元素，保存到结果集中 List<Integer> tmp = new ArrayList<>(); tmp.add(nums[left]); tmp.add(nums[right]); ans.add(tmp);
// 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 因为题目要求结果集合不重复 while (left < right && nums[left] == numLeft) { left++; }
// 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 因为题目要求结果集合不重复 while (left < right && nums[right] == numRight) { right--; } } else if (target < sum) { // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 减少不必要的循环 while (left < right && nums[right] == numRight) { right--; } } else if (target > sum) { // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 减少不必要的循环 while (left < right && nums[left] == numLeft) { left++; } } }
return ans; }}
复制代码
so easy，肯定一把过，提交下看看结果：
发现居然在执行倒数第三个测试用例时失败了，因为输入的 target 是一个比较大的负值，而 nums[i] 也是一个比较大的正整数，而我们的代码中有 target - nums[i] 这么一段代码，会导致整型溢出（target 是 Integer 类型），因此，最简单的解决办法是把 target 的类型修改成 Long，调整后的代码如下：
class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { // 数组排序 Arrays.sort(nums); // 数组长度 int len = nums.length;
Long targetLong = (long)target;
// 结果集合 List<List<Integer>> ans = new ArrayList<>(); List<Integer> tmp = null;
for (int i=0; i<len; ++i) { // 固定nums[i] List<List<Integer>> res = threeSum(nums, i+1, targetLong - nums[i]); for (List<Integer> item : res) { item.add(nums[i]); ans.add(item); }
// 跳过重复元素 while (i < len-1 && nums[i] == nums[i+1]) { ++i; } } return ans; }
/** * 三数之和，输入数组已经排好序 * 在数组nums中找出所有和等于target的不重复三元组 */ public List<List<Integer>> threeSum(int[] nums, int start, long target) { // 数组长度 int len = nums.length;
// 结果集合 List<List<Integer>> ans = new ArrayList<>(); // 结果集合中的某一个三元组 List<List<Integer>> tmp = null;
for (int i = start; i < len; ++i) { // 固定nums[i]作为第一个元素，通过twoSum得到所有满足条件的另外两个元素 // 然后一起组成一个三元组，注意，twoSum 入参中，数组开始的下标start要设置 // 为i+1，不能再包含 nums[i] tmp = twoSum(nums, i + 1, target - nums[i]); for (List<Integer> item : tmp) { item.add(nums[i]); // 找到符合条件的一个三元组，并添加到结果结合中 ans.add(item); }
// 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 while (i < len - 1 && nums[i] == nums[i + 1]) { ++i; } } return ans; }
/** * 两数之和 * 输入数组nums已经排好序，无需重复排序，且下标从start开始 * 也就是找出从start开始到nums.length之间，所有满足和为target的不重复二元组 */ public List<List<Integer>> twoSum(int[] nums, int start, long target) { // 数组长度 int len = nums.length;
// 左指针，指向数组开头 int left = start;
// 右指针，指向数组尾部 int right = len - 1;
// 返回结果 List<List<Integer>> ans = new ArrayList<>();
// 开始循环 while (left < right) { int sum = nums[left] + nums[right];
// 保存当前循环的第一个数，后面用于判重 int numLeft = nums[left];
// 保存当前循环的第二个数，后面用于判重 int numRight = nums[right];
if (target == sum) { // 找到目标元素，保存到结果集中 List<Integer> tmp = new ArrayList<>(); tmp.add(nums[left]); tmp.add(nums[right]); ans.add(tmp);
// 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 因为题目要求结果集合不重复 while (left < right && nums[left] == numLeft) { left++; }
// 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 因为题目要求结果集合不重复 while (left < right && nums[right] == numRight) { right--; } } else if (target < sum) { // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 减少不必要的循环 while (left < right && nums[right] == numRight) { right--; } } else if (target > sum) { // 当出现类似 [1,1,2,2,2,3,3] 这样有重复元素的数组时，要跳过重复元素 // 减少不必要的循环 while (left < right && nums[left] == numLeft) { left++; } } }
return ans; }}
复制代码
好，这种解法的时间复杂度是 O(N³)。
划线
评论
复制
发布于: 刚刚阅读数: 4
版权声明: 本文为 InfoQ 作者【面试官问】的原创文章。
原文链接:【http://xie.infoq.cn/article/fa9be3652c8b7823c887f1d0c】。文章转载请联系作者。
面试官问
关注
公众号：面试官问 2017.10.20 加入
还未添加个人简介
评论