Two Sum. Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that e…

ThreeSum.cc

class Solution {
public:
    
    void twoSum(int first, int last, const vector<int> sVec, int target, vector<vector<int> > & res)
    {
        int prei = INT_MAX;
        int prej = INT_MAX;
        while(first < last)
        {
            int i = sVec[first];
            int j = sVec[last];
            int sum = i+j;
            if(sum == target)
            {
                if(i == prei && j == prej)
                {
                    first++;
                    last--;
                    continue;
                }
                vector<int> newPair;
                newPair.push_back(i);
                newPair.push_back(j);
                res.push_back(newPair);
                prei = i;
                prej = j;
                first++;
                last--;
            }else if(sum < target)
            {
                first++;
            }else
            {
                last--;
            }
        }
    }
    
    void threeSum(int last, const vector<int> sVec, int target, vector<vector<int> > & res)
    {
        int valPre = INT_MAX;
        for(int i = last; i>=0; --i)
        {
            int val = sVec[i];
            if(val == valPre)
                continue;
            
            valPre = val;
            size_t preSize = res.size();
            twoSum(0, i-1, sVec, target-val, res); // two sum
            for(int j = preSize; j < res.size(); ++j)
            {
                res[j].push_back(val);
            }
        }
    }
    
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        sort(num.begin(), num.end());
        
        vector<vector<int> > res;
        int preVal = INT_MAX;
        for(int i = num.size()-1; i>=0; --i)
        {
            int val = num[i];
            if(val == preVal)
                continue;
                
            preVal = val;
            size_t preSize = res.size();
            threeSum(i-1, num, target-val, res); // three sum
            for(int j = preSize; j < res.size(); ++j)
            {
                res[j].push_back(val);
            }
        }
        
        return res;
    }
};

ThreeSumClosest.cc

class Solution {
public:

    int twoSumClosest(int first, int last, const vector<int> &sortVec, int target)
    {
        int tDiff = INT_MAX;
        int tT = INT_MAX;
        while(first < last)
        {
            int i = sortVec[first];
            int j = sortVec[last];
            int sum = i+j;
            if(sum == target)
            {
                return target;
            }else if(sum < target)
            {
                int diff = target - sum;
                if(diff < tDiff)
                {
                    tDiff = diff;
                    tT = sum;
                }
                first++;
            }else
            {
                int diff = sum - target;
                if(diff < tDiff)
                {
                    tDiff = diff;
                    tT = sum;
                }
                last--;
            }
        }
        
        return tT;
    }
    
    int threeSumClosest(vector<int> &num, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        
        sort(num.begin(), num.end());
        
        int preVal = INT_MAX;
        int tDiff = INT_MAX;
        int tT = INT_MAX;
        for(int i = 0; i<(int)num.size(); ++i)
        {
            int val = num[i];
            if(val == preVal || (int)num.size()-1<=i+1)
                continue;
            int tSum = twoSumClosest(i+1, (int)num.size()-1, num, target - val);
            int sum = tSum + val;
            if(sum == target)
                return sum;
            else if(sum < target)
            {
                int diff = target - sum;
                if(diff < tDiff)
                {
                    tDiff = diff;
                    tT = sum;
                }
            }else // sum > target
            {
                int diff = sum - target;
                if(diff < tDiff)
                {
                    tDiff = diff;
                    tT = sum;
                }
                return tT; // no need to compare
            }
        }
        
        return tT;
    }
};

TwoSum.cc

class Solution {
public:
    struct numIdx
    {
        int val;
        int idx;
        bool operator < (const numIdx &obj) const
        {
            return val < obj.val;
        }
        
        numIdx(int val, int idx):val(val),idx(idx)
        {}
    };
    vector<int> twoSum(vector<int> &numbers, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        std::vector<int> res;
        vector<numIdx> num; 
        num.reserve(numbers.size());
        for(size_t i = 0; i<numbers.size(); ++i)
        {
            num.push_back(numIdx(numbers[i],(int)i+1));
        }
        
        sort(num.begin(), num.end()); // sort
        
        size_t i = 0, j = num.size()-1;
        while(i<j)
        {
            int sum = num[i].val + num[j].val;
            if(sum == target)
            {
                int idxi = num[i].idx;
                int idxj = num[j].idx;
                if(idxi<idxj)
                {
                    res.push_back(idxi);
                    res.push_back(idxj);
                }else
                {
                    res.push_back(idxj);
                    res.push_back(idxi);
                }
                break;
            }else if(sum < target)
            {
                i++;
            }else
            {
                j--;
            }
        }
        
        return res;
    }
};