15. 3Sum

https://leetcode.com/problems/3sum/

Problem

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.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

• 0 <= nums.length <= 3000

• -105 <= nums[i] <= 105

Solution

1. $O(N^2)$ Using Hash map

class Solution {
public:
   vector<vector<int>> threeSum(vector<int>& nums) {
       vector<vector<int>> triplets;
       if (nums.empty()) return triplets;
       sort(nums.begin(), nums.end());
       unordered_set<int> seen; seen.reserve(nums.size());
       for (int i = 0; i < nums.size(); ++i) {
           if (i > 0 && nums[i - 1] == nums[i]) continue;
           for (int j = i + 1; j < nums.size(); ++j) {
               if (seen.find(-nums[j]-nums[i]) != seen.end()) {
                   triplets.push_back({nums[i], -nums[j]-nums[i], nums[j]});
                   while (j + 1 < nums.size() && nums[j] == nums[j + 1]) ++j;
               }
               seen.insert(nums[j]);
           }
           seen.clear();
       }
       return triplets;
   }
};

2. $O(N^2)$ Using two pointers

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> triplets;
        sort(nums.begin(), nums.end());
        if (nums.size() < 3) return triplets;
        for (int i=0; i<nums.size(); i++){
            if (i != 0 && nums[i]==nums[i-1]) continue;
            int j=i+1, k=nums.size()-1;
            while (j<k){
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0){
                    j++;
                } else if (sum > 0) {
                    k--;
                } else {
                    triplets.push_back({nums[i], nums[j], nums[k]});
                    k--; j++;
                    while(k > 0 && nums[k] == nums[k+1]) k--;
                    while(j < nums.size() && nums[j] == nums[j-1]) j++;
                    
                }
            }
        }
        return triplets;
    }
};

• #twopointer

• #hash