面试热题(三数之和)

这篇具有很好参考价值的文章主要介绍了面试热题(三数之和)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

       梦开始的地方(两数之和),这其实和两数之和的做法大同小异,三数之和我们开始将其拆分成一数枚举,剩余两数凑结果即可

面试热题(三数之和),热题Hot100,算法,数据结构,排序算法

        因为我们利用类似于滑动窗口类似的技巧,所以我们必须要求该数组是一个有序的数组,所以我们先要对数组进行排序

 Arrays.sort(nums);

然后对数组中的每个元素进行枚举,相当于确定一个数

 //因为我们这是三数之和,所以我们的第一个数醉倒可以枚举到倒数第三个数
 for (int i = 0; i < nums.length - 2; i++) {}

因为在遍历的时候,我们可以优先的对过程进行剪枝操作:

1.如果前面3个数相加已经大于零,后面的数就不可能在等于零,故可以剪去

2.如果第一个数加上最大的两个数都小于零,最大的数都小于零,更何况中间的数呢?故可以进行剪去

3.因为题目中不允许我们又重复的结果出现,我们也可以将其进行剪去

那么我们就可以得到如下:

             int x = nums[i];
            //如果前三个数之和大于零,后面的数之和就不可能有等于零的情况
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            //加上两个最大的值也小于零,直接跳过这个x值
            if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {
                continue;
            }
            //为了避免重复的情况的发生,如果相等则直接跳过
            if (i>0&&nums[i] == nums[i - 1]) {
                continue;
            }

面试热题(三数之和),热题Hot100,算法,数据结构,排序算法

       现在的问题就转换成在固定的区间内找到满足target的两数之和,通过双指针不断的从两边收缩进行求解

            int j = i + 1;
            int k = n-1;
            while (j < k) {
                //两数和
                int sum = x + nums[k] + nums[j];
                //如果大于,说明k指向的数太大了,往左移
                if (sum > 0) {
                    k--;
                //如果小于,说明j指向的数太小了,往右移
                } else if (sum < 0) {
                    j++;
                 //如果相等,先将3个符合条件的数添加到list中去
                } else {
                    list.add(Arrays.asList(x,nums[j],nums[k]));
                    //为了避免结果重复,左指针碰到相邻重复的直接跳过
                    while (j < k && nums[j] == nums[j+1]) {
                        j++;
                    }
                    j++;
                    // //为了避免结果重复,右指针碰到相邻重复的直接跳过
                    while (j < k && nums[k] == nums[k-1]) {
                        k--;
                    }
                     k--;
                }
            }

源码如下:文章来源地址https://www.toymoban.com/news/detail-650596.html

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        //先对入参进行判断,如果nums为空,直接返回
        if (nums == null || nums.length == 0) {
            return list;
        }
        Arrays.sort(nums);
        int n = nums.length;
        //枚举每一个元素,设置两个指针进行跑
        for (int i = 0; i < nums.length - 2; i++) {
            int x = nums[i];
            //如果前三个数之和大于零,后面的数之和就不可能有等于零的情况
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            //加上两个最大的值也小于零,直接跳过这个x值
            if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {
                continue;
            }
            //为了避免重复的情况的发生,如果相等则直接跳过
            if (i>0&&nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = n-1;
            while (j < k) {
                int sum = x + nums[k] + nums[j];
                if (sum > 0) {
                    k--;
                } else if (sum < 0) {
                    j++;
                } else {
                    list.add(Arrays.asList(x,nums[j],nums[k]));
                    while (j < k && nums[j] == nums[j+1]) {
                        j++;
                    }
                    j++;
                    while (j < k && nums[k] == nums[k-1]) {
                        k--;
                    }
                     k--;
                }
            }

        }
        return list;
    }

到了这里,关于面试热题(三数之和)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode热题100.两数之和

    给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1: 输入:nums =

    2024年01月16日
    浏览(36)
  • 【LeetCode热题100】两数之和 C++

    给定一个整数数组  nums  和一个整数目标值  target ,请你在该数组中找出  和为目标值  target   的那  两个  整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1:

    2024年02月06日
    浏览(35)
  • 面试经典题---15.三数之和

    15.三数之和 我的解法: 预处理 当nums大小小于3时,直接返回空的res 对nums排序后,若首元素小于0或末尾元素大于0,也直接返回空的res 双指针法找出三元组(nums[i]、nums[left]和nums[right]) i从0开始取值,对于每个i,判断是否存在三元组和为0的left(初值为i+1)和right(初值为

    2024年01月20日
    浏览(31)
  • 面试算法100:三角形中最小路径之和

    在一个由数字组成的三角形中,第1行有1个数字,第2行有2个数字,以此类推,第n行有n个数字。例如,下图是一个包含4行数字的三角形。如果每步只能前往下一行中相邻的数字,请计算从三角形顶部到底部的路径经过的数字之和的最小值。从三角形顶部到底部的路径数字之和

    2024年01月16日
    浏览(43)
  • 《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数

    本期给大家带来的是是《 LeetCode 热题 HOT 100 》第四题—— 寻找两个正序数组的中位数的 题目讲解 !!!() 本文目录 💥题意分析 💥解题思路: 1、直接法  (❌) 2、归并思想 (❌) ①《LeetCode》第88题——合并两个有序数组 3、二分查找(✔️) 整体思想: 题目如下

    2023年04月27日
    浏览(40)
  • LeetCode(Hot100)——1:两数之和

    利用两次for循环来处理, 外循环确定一个数字, 利用内循环不断求和来判断是否两数之和为target,来进行求解。 暴力求解的时间复杂度是O(n2) 哈希的时间复杂度为O(1),利用哈希容器map降低时间复杂度 遍历数组 nums,i 为当前下标,每个值都判断map中是否存在 target-nums[i] 的

    2024年02月04日
    浏览(32)
  • 面试热题(两数之和)

    给定一个整数数组  nums  和一个整数目标值  target ,请你在该数组中找出  和为目标值  target   的那  两个  整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。        

    2024年02月13日
    浏览(37)
  • 【leetcode面试经典150题】29.三数之和(C++)

    【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致) 给你一个整数数组 

    2024年04月13日
    浏览(39)
  • 【算法】排序+双指针——leetcode三数之和、四数之和

    三数之和 (1)排序+双指针   算法思路: 和之前的两数之和类似,我们对暴力枚举进行了一些优化,利用了 排序+双指针 的思路:   我们先排序,然后固定⼀个数 a ,接着我们就可以在这个数后面的区间内,使用之前两数之和使用的算法,快速找到两个数之和和固定的

    2024年02月13日
    浏览(51)
  • 算法刷题-哈希表-三数之和

    用哈希表解决了两数之和,那么三数之和呢? 力扣题目链接 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意: 答案中不可以包含重复的三元组。 示例: 给定数组 nums = [-1, 0, 1, 2

    2024年02月09日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包