Leet 15 – 3Sum

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

My Solution:

The simple idea I have is to loop over every i,i+1,i+2 and compare them with 
i +1, i+2, i+3 and i+2,i+3,i+4, and i+3,i+4,i+5, and i+4,i+5,i+6.
But first and for most sorting the array will provide
easy traversal and logic to figure out which direction to check arithmetically,
and also easy edge case prevention, 
such as duplicates and only positive numbers.



Class Solution{
public:
vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    int vector_length = nums.size();
    vector<int> temp; // for emplacing the vectors to the result vector of vectors
    int i = -1;
    while (i < vector_length) {
        i++;
        if (nums[i] > 0) break;
        int low = i + 1;
        int high = number_length - 1;
        while (low < high) {
            while (low < high && nums[high] + nums[low] > -nums[i]) high--;
            while (low < high && nums[high] + nums[low] < -nums[i]) low++;
            if (low < high && nums[high] + nums[low] == -nums[i]) {
               temp.clear();
               temp.push_back(nums[i]);
               temp.push_back(nums[low]);
               temp.push_back(nums[high]);
               result.push_back(temp);
               while (nums[high-1] == nums[high]) high--;
               while (nums[low+1] == nums[low]) low++;
               high--;
               low++;
        }
    }
    while (nums[i+1]==nums[i]) i++;
}
return result;
}
}

Time Complexity:

O(nlog(n) +n^2) – O(nlog(n))  because I’m sorting the vectors + O(n*n) because we are traversing every vector against all other vectors.

Space Complexity:

O(1) -Constant because I create a list of vectors, ahead of time.