Leetcode 15 : 3Sum Solution

Problem Statement could be found @https://leetcode.com/problems/3sum/

Approach -
A brute force solution like below is simple
1. Fix one element and then find next 2 elements such that sum of 3 elements becomes zero
2. In a random shuffled array above point would be O(n*n*n)

We can try optimizing above
1. Let us try to sort the array first O(nlogn)
2. Now start from first  element (lets say i), pick (i+1)th element and last element. Sum of these 3 if zero then we have one solution. Otherwise, if it is less than zero, then increase (i+1) else decrease last.
3. Trying step 2 in a for loop would give us result but it would have duplicates
4. We can eliminate duplicates by few additional checks as in code below



Code

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> retVec;
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();i++){
         
            int a =  nums[i];
            if (a >0){
                break;
            }else {
                while((i<nums.size()) && (i>0) && (nums[i] == nums[i-1] )){
                    i++;
                }
            }
            a = nums[i];
            int j = i+1;
            int k = nums.size()-1;
           
            while(j <k){
                int comp = a + nums[j] + nums[k];
                if (comp == 0){
                    vector<int> v;
                    v.push_back(a);
                    v.push_back(nums[j]);
                    v.push_back(nums[k]);
                    retVec.push_back(v);
                    j++;
                    k--;
                    while ( (j <k) &&(nums[j] == nums[j-1]) ){
                        j++;
                    }
                    while ( (j <k) &&(nums[k] == nums[k+1]) ){
                        k--;
                    }
                 
                }
                if (comp < 0){
                    j++;
                }
                if (comp>0){
                    k--;
                }
               
            }
        }
        return retVec;
    }
};