【leetcode面试经典150题】29.三数之和(C++)

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

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

【题目描述】

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

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

注意:答案中不可以包含重复的三元组。文章来源地址https://www.toymoban.com/news/detail-849386.html

【示例一】

输入: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] 。
注意,输出的顺序和三元组的顺序并不重要。

【示例二】

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

【示例三】

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

【提示及数据范围】

  • 3 <= nums.length <= 3000
  • -10的5次方 <= nums[i] <= 10的5次方

【代码】

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int l = i+1, r = n-1;
            while (l < r) {
                if (nums[i]+nums[l]+nums[r] < 0) {
                    ++l;
                } else if (nums[i]+nums[l]+nums[r] > 0) {
                    --r;
                } else {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    while (l+1 < n && nums[l] == nums[++l]);
                    while (r-1 > 0 && nums[r] == nums[--r]);
                }
            }
        }
        return ans;
    }
};

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

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

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

相关文章

  • 【算法】排序+双指针——leetcode三数之和、四数之和

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

    2024年02月13日
    浏览(51)
  • Leetcode每日一题:15. 三数之和(2023.7.9 C++)

    目录 15. 三数之和 题目描述: 实现代码与解析: 双指针 原理思路:         给你一个整数数组  nums  ,判断是否存在三元组  [nums[i], nums[j], nums[k]]  满足  i != j 、 i != k  且  j != k  ,同时还满足  nums[i] + nums[j] + nums[k] == 0  。请 你返回所有和为  0  且不重复的三元组

    2024年02月13日
    浏览(39)
  • 【LeetCode-经典面试150题-day12】

    20.有效的括号 题意: 给定一个只包括  \\\'(\\\' , \\\')\\\' , \\\'{\\\' , \\\'}\\\' , \\\'[\\\' , \\\']\\\'  的字符串  s  ,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。 【输入样例】s=\\\"

    2024年02月11日
    浏览(39)
  • LeetCode面试经典150题(day 2)

    26. 删除有序数组中的重复项 难度: 简单    给你一个  升序排列  的数组  nums  ,请你  原地  删除重复出现的元素,使每个元素  只出现一次  ,返回删除后数组的新长度。元素的  相对顺序  应该保持  一致  。然后返回  nums  中唯一元素的个数。 考虑  nums  的唯一

    2024年02月11日
    浏览(46)
  • 【LeetCode-经典面试150题-day11】

    目录 128.最长连续序列  228.汇总区间  56.合并区间  57.插入区间  452.用最少数量的箭引爆气球   128.最长连续序列 题意: 给定一个未排序的整数数组  nums  ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为  O(n)   的算法

    2024年02月12日
    浏览(42)
  • LeetCode150道面试经典题-- 加一(简单)

    给你一个非负整数 x ,计算并返回  x  的 算术平方根 。 由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。 注意: 不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1: 输入:x=4 输出:2   示例 2: 输入: x = 8 输出: 2 解释: 8 的

    2024年02月12日
    浏览(37)
  • 【LeetCode-面试经典150题-day14】

      目录 19.删除链表的倒数第N个结点  82.删除排序链表中的重复元素Ⅱ  61. 旋转链表  86.分隔链表  146.LRU缓存 19.删除链表的倒数第N个结点 题意: 给你一个链表,删除链表的倒数第  n   个结点,并且返回链表的头结点。 【输入样例】head = [1,2,3,4,5],n=2 【输出样例】[1,2,3,5

    2024年02月11日
    浏览(43)
  • 【LeetCode-面试经典150题-day23】

    目录 108. 将有序数组转换为二叉搜索树  148.排序链表  427.建立四叉树  23.合并K个升序链表   108. 将有序数组转换为二叉搜索树 题意: 给你一个整数数组  nums  ,其中元素已经按  升序  排列,请你将其转换为一棵  高度平衡  二叉搜索树。 高度平衡  二叉树是一棵满足「

    2024年02月09日
    浏览(43)
  • LeetCode面试经典150题(day 1)

    LeetCode是一个免费刷题的一个网站,想要通过笔试的小伙伴可以每天坚持刷两道算法题。 接下来,每天我将更新LeetCode面试经典150题的其中两道算法题,一边巩固自己,一遍希望能帮助到有需要的小伙伴。 88.合并两个有序数组 给你两个按  非递减顺序  排列的整数数组  nu

    2024年02月11日
    浏览(36)
  • LeetCode150道面试经典题-- 快乐数(简单)

    编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」  定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如果这个过程 结果为  1,那么这个数就是快乐数。 如果

    2024年02月12日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包