15. 三数之和

约定不等于承诺〃 2022-08-31 04:42 246阅读 0赞

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

提示：

0 <= nums.length <= 3000
-105 <= nums[i] <= 105

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) {
  4.         sort(nums.begin(),nums.end());
  5.         unordered_map<int,int> mp;
  6.         for(int i = 0 ;i<nums.size();i++)
  7.         {
  8.             mp[nums[i]]++;
  9.         }
  10.         vector<vector<int>> ret;
  11.         int pre_i=-9999999,pre_j=-9999999,pre_k=-9999999;
  12.         for(int i = 0;i<nums.size();i++)
  13.         {
  14.             for(int j = i+1;j<nums.size();j++)
  15.             {
  16.                 int k = -nums[i]-nums[j];
  17.                 mp[nums[i]]--,mp[nums[j]]--;
  18.                 auto it = mp.find(k);
  19.                 if(k>=nums[j]&&it!=mp.end()&&it->second>0&&((pre_i < nums[i])||(pre_i==nums[i]&&pre_j<nums[j])||(pre_i==nums[i]&&pre_j==nums[j]&&pre_k<k)))
  20.                 {
  21.                     ret.push_back(vector<int>({nums[i],nums[j],k}));
  22.                     pre_i = nums[i],pre_j = nums[j], pre_k = k;
  23.                 }
  24.                 mp[nums[i]]++,mp[nums[j]]++;
  25.             }
  27.         }
  28.         return ret;
  29.     }
  30. };

发表评论

表情：
评论列表 （有 0 条评论，246人围观）

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

相关阅读

    相关 15.三数之和

    [题目][Link 1] 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足

    た 入场券た 入场券/ 0 赞/ 23 阅读

    相关 15. 三数之和

    链接：https://leetcode-cn.com/problems/3sum 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，

    亦凉亦凉/ 0 赞/ 216 阅读

    相关 15.三数之和

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

    ╰半橙微兮°╰半橙微兮°/ 0 赞/ 424 阅读