写点什么

【萌新解题】三数之和

作者:面试官问
  • 2022 年 7 月 17 日
  • 本文字数:2460 字

    阅读完需:约 8 分钟

【萌新解题】三数之和

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

题目描述

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


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

解题说明

本题要求找出整数数组中符合条件的三元组,使三元组中三个元素之和等于 0,而且不能包含重复元素,因此,我们可以先对数组进行排序,对于相同的元素,排序后是挨在一起的,类似 [1,1,2,2,2,3,3],这样我们可以很容易跳过重复元素,具体可以参考https://mp.weixin.qq.com/s/ZtEkRcQ2ujHYmUO3BlcXiw


为了求出三元组,我们可以采用分而治之的思想,遍历数组,在每次循环中,先固定其中一个元素,然后在数组中剩下的元素中求出符合条件的二元组,那这个问题就退化为两数之和了,只不过在https://mp.weixin.qq.com/s/ZtEkRcQ2ujHYmUO3BlcXiw 这个题目中,结果返回的是符合条件的两个元素的下标,不是元素值,而且数组是从 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 }}
复制代码


其中两数之和我们参考https://mp.weixin.qq.com/s/ZtEkRcQ2ujHYmUO3BlcXiw ,改造成如下形式即可:


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; }}
复制代码


发布于: 刚刚阅读数: 4
用户头像

面试官问

关注

公众号:面试官问 2017.10.20 加入

还未添加个人简介

评论

发布
暂无评论
【萌新解题】三数之和_面试_面试官问_InfoQ写作社区