LeetCode 15. 3Sum (三数之和)

超、凢脫俗 2022-05-11 00:20 141阅读 0赞

题目描述：

给定一个包含 *n* 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 *a，b，c ，*使得 *a + b + c =* 0 ？找出所有满足条件且不重复的三元组。

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    
    满足要求的三元组集合为：
    [
      [-1, 0, 1],
      [-1, -1, 2]
    ]

Accepted C++ Solution:

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector< vector<int> > res;
            std::sort(nums.begin(), nums.end());    //先将数组变为有序的
            
            for (int i = 0; i < nums.size(); i++) {
                int target = -nums[i];
                int front = i+1;
                int back = nums.size() - 1;
                
                while(front < back) {
                    int sum = nums[front] + nums[back];
                    
                    if (sum < target)
                        front++;
                    
                    else if (sum > target)
                        back--;
                    
                    else {
                        vector<int> solu(3,0);
                        solu[0] = nums[i];
                        solu[1] = nums[front];
                        solu[2] = nums[back];
                        res.push_back(solu);
                        
                        while(front < back && nums[front] == solu[1])   front++;    //跳过重复元素
                        while(front < back && nums[back] == solu[2])    back--;    //跳过....
                    }
                }
                while(i+1 < nums.size() && nums[i+1] == nums[i])    //跳过重复元素
                    i++;
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关 15. 3Sum(三数之和——）

我还以为我写了blog3sum，结果没找都。那就再复习一遍给定阵列nums的Ñ整数，在那里元件a，b，c 在nums使得a + b + c = 0 在给出零总和的数组中找

た入场券/ 2022年12月02日 11:00/ 0 赞/ 112 阅读

相关 [LeetCode]15. 3Sum三数之和

Given an array `nums` of n integers, are there elements a, b, c in `nums` such that a \+

超、凢脫俗/ 2022年10月02日 14:57/ 0 赞/ 139 阅读

相关 leetcode 15,18. 3Sum,4Sum | 15,18. 三数之和,四数之和（Java）

15. 3Sum [https://leetcode.com/problems/3sum/][https_leetcode.com_problems_3sum] ![

Bertha 。/ 2022年08月30日 00:49/ 0 赞/ 138 阅读

相关 leetcode 15. 三数之和

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

深碍√TFBOYSˉ_/ 2022年05月14日 07:51/ 0 赞/ 166 阅读

相关 LeetCode 15. 3Sum (三数之和)

题目描述：给定一个包含 n 个整数的数组 `nums`，判断 `nums` 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的

超、凢脫俗/ 2022年05月11日 00:20/ 0 赞/ 142 阅读

相关 leetcode第15题 3Sum(三数之和)

比较简单的一道题，题目的大意是说： > 给定一个长度为n的整数数组nums，从数组中找出所有不重复的（三个数相加等于0的组合）。 > 注意，仅字典序不同的、包含数字相同

我会带着你远行/ 2022年03月08日 05:08/ 0 赞/ 197 阅读

相关 leetcode:15.三数之和

题目描述：给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元

野性酷女/ 2022年02月28日 11:18/ 0 赞/ 194 阅读

相关 LeetCode-15.三数之和

题目给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

Dear 丶/ 2022年01月31日 08:43/ 0 赞/ 190 阅读

相关 15. 3Sum[M]三数之和

题目 Given an array nums of n integers, are three elements a, b, c in nums such that a+

野性酷女/ 2021年11月23日 07:04/ 0 赞/ 288 阅读

相关 Leetcode 15. 三数之和

文章目录 1. 对撞指针 1.1 思路 1.2 复杂度 1.3 代码 1. 对撞指针 1.1 思路首先对数组

我会带着你远行/ 2021年10月13日 15:26/ 0 赞/ 326 阅读