Leetcode: 3sum (Analysis & solution)

PROBLEM:

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:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• 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)

Show Tags

Show Similar Problems

Based on the two sum problem, add a outer for loop to implement the third sum. 

//codes

class Solution {

public:

       vector<vector<int>> threeSum(vector<int>& nums) {

              vector<vector<int>> result;

              if (nums.size() < 3)return result;

              map<vector<int>, int> map_tmp;

              sort(nums.begin(), nums.end());//sort

             

              for (int i = 0; i < nums.size(); i++){

                     vector<int> nums_tmp = nums;

                     nums_tmp.erase(nums_tmp.begin() + i);

                     int remains = 0 - nums[i];

                     //using two sum

                     vector<int>::iterator start = nums_tmp.begin();

                     vector<int>::iterator ending = nums_tmp.end();

                     --ending;

                    

                     for (int j = i; j < nums_tmp.size()-1; j++){ //NOTE: j < nums_tmp.size()-1

                           int sum = (*start) + (*ending);

                           if (sum > remains) --ending;

                           else if (sum < remains) ++start;

                           else {

                                  //sorting the three

                                  if (nums[i] >= (*ending)) {

                                         map_tmp[{(*start), (*ending), nums[i]}] = j;

                                  }

                                  else if (nums[i] <= (*start)) {

                                         map_tmp[{nums[i], (*start), (*ending)}] = j;

                                  }

                                  else {

                                         map_tmp[{(*start), nums[i], (*ending)}] = j;

                                  }

                                        

                           }

                     }

              }

             

              map<vector<int>, int>::iterator it = map_tmp.begin();

              for (int n=0; it!=map_tmp.end(); it++, n++){

                     result.push_back(it->first);

              }

              return result;

       }

};