3Sum

Problem: Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Solution:

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i, j, k, sum;
        vector<vector<int> > solution;
        sort(num.begin(), num.end());
        for (i = 0; i < num.size(); i++) {
            j = i+1;
            k = num.size() - 1;
            while (j < k) {
                sum = num[i] + num[j] + num[k];
                if (sum == 0) {
                    vector<int> ans(3);
                    ans[0] = num[i];
                    ans[1] = num[j];
                    ans[2] = num[k];
                    j++;
                    k--;
                    if (find(solution.begin(), solution.end(), ans) == solution.end())
                        solution.push_back(ans);
                } else if (sum < 0) {
                    j++;
                } else if (sum > 0) {
                    k--;
                }
            }
        }
        return solution;
    }
};

=============== Another solution ==============
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> sol;
        sort(nums.begin(), nums.end());
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int first = nums[i];
            int idx_2 = i + 1, idx_3 = size - 1;
            while (idx_2 < idx_3) {
                if (nums[idx_2] + nums[idx_3] == -first) {
                    vector<int> ans;
                    ans.push_back(first);
                    ans.push_back(nums[idx_2]);
                    ans.push_back(nums[idx_3]);
                    sol.push_back(ans);
                    while (idx_2++ < idx_3) {
                        if (nums[idx_2] != nums[idx_2 - 1]) {
                            break;
                        }
                    }
                    while (idx_2 < idx_3--) {
                        if (nums[idx_3] != nums[idx_3 + 1]) {
                            break;
                        }
                    }
                } else if (nums[idx_2] + nums[idx_3] < -first) {
                    idx_2++;
                } else {
                    idx_3--;
                }
            }
        }
        return sol;   
    }
};


========= fizzbuzzed.com/top-interview-questions-1/

vector<vector<int>> threeSum(vector<int>& nums) {
  vector<vector<int>> output;
  sort(nums.begin(), nums.end());
  for (int i = 0; i < nums.size(); ++i) {
    // Never let i refer to the same value twice to avoid duplicates.
    if (i != 0 && nums[i] == nums[i - 1]) continue;
    int j = i + 1;
    int k = nums.size() - 1;
    while (j < k) {
      if (nums[i] + nums[j] + nums[k] == 0) {
        output.push_back({nums[i], nums[j], nums[k]});
        ++j;
        // Never let j refer to the same value twice (in an output) to avoid duplicates
        while (j < k && nums[j] == nums[j-1]) ++j;
      } else if (nums[i] + nums[j] + nums[k] < 0) {
        ++j;
      } else {
        --k;
      }
    }
  }
  return output;