当前位置：网站首页>【萌新解题】四数之和

【萌新解题】四数之和

2022-07-17 21:35:00 【InfoQ】

关于我：微信公众号：
面试官问
，原创高质量面试题，始于面试题，但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目，本题是力扣第 18 题：四数之和：https://leetcode.cn/problems/4sum/。

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且
不重复
的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d&nbsp;< 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，肯定一把过，提交下看看结果：

null
发现居然在执行倒数第三个测试用例时失败了，因为输入的 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³)。
原网站

版权声明
本文为[InfoQ]所创，转载请带上原文链接，感谢
https://xie.infoq.cn/article/fa9be3652c8b7823c887f1d0c

边栏推荐

猜你喜欢

随机推荐