15. 3Sum-白红宇

15. 3Sum

阅读量：7004 次

发布时间：2019-06-27

本文共 1523 字，大约阅读时间需要 5 分钟。

15. 3Sum

题目

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.Note: The solution set must not contain duplicate triplets.For example, given array S = [-1, 0, 1, 2, -1, -4],A solution set is:[  [-1, 0, 1],  [-1, -1, 2]]

解析

想写出一次能AC的代码真不容易！

很多细节问题，和sumtwo不一样的是：这次有重复元素；sumtwo假定没有重复元素，且只需要返回下标值

要跳过重复的元素

class Solution_15 {public:    void twosum(vector
    
     
      >& vecs,vector
      
       & nums,int start, int target)    {        vector
       
         ans;        int end = nums.size() - 1;        while (start

> threeSum(vector

& nums) { // Time Limit Exceeded vector

> vecs; if (nums.size() <= 2) { return vecs; } sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size() - 2;++i) { if (i>0&&nums[i]==nums[i-1]) //忽略掉有重复元素的值 { continue; } twosum(vecs, nums,i+1, -nums[i]); } return vecs; // } vector

> threeSum1(vector

& nums) { // Time Limit Exceeded vector

> vecs; if (nums.size()<=2) { return vecs; } unordered_map

mp; vector

ans; for (int i = 0; i < nums.size() - 2;++i) { mp.clear(); for (int j = i + 1; j < nums.size();++j) { auto iter = mp.find(-(nums[i] + nums[j])); //查找主关键字 if (iter!=mp.end()) { ans.push_back(nums[i]); ans.push_back(iter->first); ans.push_back(nums[j]); sort(ans.begin(), ans.end()); //处理有重复元素 if (find(vecs.begin(),vecs.end(),ans)==vecs.end()) //没有元素才插入操作 { vecs.push_back(ans); } ans.clear(); } else { mp.insert(make_pair(nums[j], j)); } } } return vecs; // }};

题目来源

转载地址：http://hmutl.baihongyu.com/

你可能感兴趣的文章