# LeetCode : 0015. 3Sum (array)
###### tags:`leetcode`
> C++ Vscode be run code

#include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

class BaseVectorPrint {
    public:
        void BasePrint00(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num.at(i) << "; ";
            }
            cout << endl;
        }

        void BasePrint01(vector<int>& num) {
            for (size_t i = 0; i < num.size(); ++i) {
                cout << num[i] << "; ";
            }
            cout << endl;
        }

        void BasePrint02(vector<int>& num) {
            for (const auto &item : num) {
                cout << item << "; ";
            }
            cout << endl;
        }
        
        void TwoDimensionalPrint(vector<vector<int>> &num){
            for (int i = 0; i < num.size(); i++)
            {
                for (int j = 0; j < num[i].size(); j++)
                {
                    cout << "[" << num[i][j] << "]";
                }
                cout << endl;
            }
        }
};

class BaseSolution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(begin(nums), end(nums));
    vector<vector<int>> res;
    for (int i = 0; i < nums.size() && nums[i] <= 0; ++i)
        if (i == 0 || nums[i - 1] != nums[i]) {
            twoSumII(nums, i, res);
        }
    return res;
    }
    
    void twoSumII(vector<int>& nums, int i, vector<vector<int>> &res) {
        int lo = i + 1, hi = nums.size() - 1;
        while (lo < hi) {
            int sum = nums[i] + nums[lo] + nums[hi];
            if (sum < 0) {
                ++lo;
            } else if (sum > 0) {
                --hi;
            } else {
                res.push_back({ nums[i], nums[lo++], nums[hi--] });
                while (lo < hi && nums[lo] == nums[lo - 1])
                    ++lo;
            }
        }
    }
};
}


class Solution01 {
public:
    vector<vector<int>> threeSum(vector<int>& num) {
        sort(begin(num), end(num));
        vector<vector<int>> res;
        for (int i = 0; i < num.size() && num[i] <= 0; ++i)
            if (i == 0 || num[i - 1] != num[i]) {
                twoSum(num, i, res);
            }
        return res;
    }
    void twoSum(vector<int>& num, int i, vector<vector<int>> &res) {
// 《unordered_set it The only container for an element. 》//
        unordered_set<int> seen;
        for (int j = i + 1; j < num.size(); ++j) {
            int complement = -num[i] - num[j];                                  
// 《unordered_set.count(element) it check element it in unordered_set 》//
// 《ex : seen.count(999) , if seen have "999" return 1, 
//      else have not it , return 0》;                                  
            if         (seen.count(complement)) {
                res.push_back({num[i], complement, num[j]});
//res 2d vector , so input 1d vector font {1,2,3}
                while (j + 1 < num.size() && num[j] == num[j + 1]) {
                            ++j;
                }
            }
            seen.insert(num[j]);
                }
    }
};
    
class Solution02 {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        if(n<3) return ans;
        //check edge > 4 or not return null;
        sort(nums.begin(),nums.end());
        for(int left=0; left<n-2; left++) {
            if(nums[left]>0) return ans;
            if(left>0 && nums[left]==nums[left-1]) continue;
            int mid = left+1;
            //set first mid = left + 1
            int right = n-1;
            //set first right = array[last] = nums.size()-1 = len - 1
            while(mid<right) {
                int sum = nums[left]+nums[mid]+nums[right];
                if(sum>0) right--;
                else if(sum<0) mid++;
                else { // sum = 0 , so mid and right move edge selection.
                    ans.push_back({nums[left],nums[mid],nums[right]});
                    while(mid<right && nums[mid]==nums[mid+1]) mid++; // if have same nums jump it
                    mid++; 
                    while(mid<right && nums[right]==nums[right-1]) right--; // if have same nums jump it
                    right--;
                }
            }
        }
        return ans;
      }
};

int main(void)
{
    BaseVectorPr        int print_test;
    Solution01 ArraySoultion;

    vector<int> input_Nums = {1,3,5,-1,0,-2,-4,-5};
    vector<vector<int>> ans ;
    ans = ArraySoultion.threeSum(input_Nums);
                
    print_test.BasePrint02(input_Nums);
    print_test.TwoDimensionalPrint(ans);


    //printf("%d\n",input_Nums);
    printf("test\n");
    system("pause");
}