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

【萌新解题】三数之和

2022-07-17 00:11:00 【InfoQ】

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

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解题说明

本题要求找出整数数组中符合条件的
三元组
，使三元组中三个元素之和等于0，而且
不能包含重复元素
，因此，我们可以先对数组进行排序，对于相同的元素，排序后是挨在一起的，类似 [1,1,2,2,2,3,3]，这样我们可以很容易跳过重复元素，具体可以参考
【萌新解题】两数之和 II - 输入有序数组
。

为了求出三元组，我们可以采用分而治之的思想，遍历数组，在每次循环中，先
固定其中一个元素
，然后在数组中剩下的元素中求出符合条件的二元组，那这个问题就退化为两数之和了，只不过在
【萌新解题】两数之和 II - 输入有序数组
 这个题目中，结果返回的是符合条件的两个元素的下标，不是元素值，而且数组是从0开始查找，而在我们这个场景下，要求返回的是二元组（元素值），而且输入参数中，是从数组某个下标开始，不是固定的0开始，按照这个思路，我们可以写出代码的框架如下：

class Solution {
 public List<List<Integer>> threeSum(int[] nums) {
 //按照题目要求，是求和0的三元组，所以target传0即可
 return threeSum(nums, 0);
 }

 /**
 * 三数之和
 * 在数组nums中找出所有和等于target的不重复三元组
 */
 public List<List<Integer>> threeSum(int[] nums, int target) {
 // 首先对数组排序，这是一切的前提
 Arrays.sort(nums);

 // 数组长度
 int len = nums.length;

 // 结果集合
 List<List<Integer>> ans = new ArrayList<>();
 // 结果集合中的某一个三元组
 List<List<Integer>> tmp = null;

 for (int i = 0; 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) {
 // TODO
 }
}

其中两数之和我们参考
【萌新解题】两数之和 II - 输入有序数组
 ，改造成如下形式即可：

public class Solution {
 /**
 * 两数之和
 * 输入数组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;
 }
}

原网站

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

边栏推荐

猜你喜欢

随机推荐