◻️15. 3Sum (medium)

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

---

Solutions

Normal (Hashing)

T.C -> n^2 log m | m is variable -> it is size of set<int> hashSet

S.C -> O(n) + O(no. of unique triplets)x2 | 🍭𝐓𝐰𝐢𝐜𝐞!🍭 because we are using list of list.

Runtime TLE

// Striver

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> st;
        int n=nums.size();
        for(int i=0; i<n; i++){
            set<int> hashSet;
            for(int j=i+1; j<n; j++){
                int k = -(nums[i]+nums[j]);
                if(hashSet.find(k) != hashSet.end()){
                    vector<int>temp = {nums[i], nums[j], k};
                    sort(temp.begin(), temp.end());
                    st.insert(temp);
                }
                hashSet.insert(nums[j]);
            }
        }
        vector<vector<int>> vec(st.begin(), st.end());
        return vec;
    }
};

Optimised (2 Pointer)

Runtime 56 ms Memory 27.33 MB

```cpp
// Striver Optimised

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3)
            return {};

        vector<vector<int>> ans;
        ranges::sort(nums);      // T.C -> O(n*logn)
        for(int i=0; i+2<nums.size(); ++i){
            if(i>0 && nums[i]==nums[i-1]){continue;}
            int l=i+1, r=nums.size()-1;
            while(l<r){
                const int sum = nums[i]+nums[l]+nums[r];
                if(sum==0){
                    ans.push_back({nums[i], nums[l++], nums[r--]});
                    while(l<r && nums[l]==nums[l-1]){++l;}
                    while(l<r && nums[r]==nums[r+1]){--r;} //this will not give error as --r and ++l already happened at Line 18 -> ans.push_back({nums[i], nums[l++], nums[r--]});
                }
                else if(sum < 0){
                    ++l;
                }
                else{
                    --r;
                }
            }
        }
        return ans;
    }
};


```