twoSum && threeSum

from leetcode.com/problems

twoSum

Description:

Given an array of integers, 
  return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, 
  and you may not use the same element twice.

Example:
  Given nums = [2, 7, 11, 15], target = 9,
  Because nums[0] + nums[1] = 2 + 7 = 9,
  return [0, 1].

Possible Ans:

/* 1) insert all elements of array into a multimap<elementType, int, less<elementType> >, 
        parameter of int means index
 * 2) when inserting ith element,find element equals to target-array[i] in multimap
 * OR
 * 1) insert all elements into multimap<elementType, int, less<elementType> >, 
        parameter of int means index;
 * 2) beg = multimap.beg(), end = multimap();
 * 3) if *beg+*end==target, return vector<int>({beg->second,end->second}).
 */
vector<int> twoSum(vector<int>& nums, int target)
{
    if (nums.size() > 1)
    {
        int s = nums.size();
        multimap<int, int> mmap;
        for (int i = 0; i < s; ++i)
        {
            multimap<int, int>::iterator iter = mmap.find(target - nums[i]);
            if (iter != mmap.end())
            {
                return vector<int>({ iter->second,i });
            }
            mmap.insert(make_pair(nums[i], i));
        }
    }
    return vector<int>();
}

threeSum

Description:

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]
    ]

Possible Ans:

/* 1) sort ASC
 * 2) ith element, low = i +1, high = len(array)-1;
 * 3) in array[low,high] , this is some like twoSum problem.
 */
vector<vector<int> > threeSum(vector<int>& nums) {
    if (nums.size() < 3)
    {
        return vector<vector<int> >();
    }
    int len = nums.size();
    sort(nums.begin(), nums.end());

    vector<vector<int> > res;

    for (int i = 0; i < len - 2; ++i)
    {
        if (nums[i] > 0)
        {
            break;
        }
        if (i > 0 && nums[i] == nums[i - 1] )
        {
            continue;
        }
        int low = i + 1;
        int high = len - 1;
        int target = -nums[i];
        while (low < high)
        {
            while (low < high && nums[low] + nums[high] < target)
            {
                ++low;
            }
            while (low < high && nums[low] + nums[high] > target)
            {
                --high;
            }
            if (low < high && nums[low] + nums[high] == target)
            {
                res.push_back({ nums[i], nums[low],nums[high] });
                ++low;
                --high;
                /* deal with duplicate elements */
                while (low < high && nums[low] == nums[low - 1])
                {
                    ++low;
                }
                while (low < high && nums[high] == nums[high + 1])
                {
                    --high;
                }
            }
        }
    }
    return res;
}