Lintcode: 3 Sum Closest

Based on 3 sum problem, just need to return sum. So we don't need to consider repetitions, which makes things much easier.
In 3 sum problem, we don't consider hashmap because repetitions will be harder to avoid.
In this problem, we don't consider hashmap because the close sum is a vague value which cannot be searched by hashmap.

Same solution like 3 sum problem:
First sorting, then use three pointers, one pointer iterates each element, other two pointers squeeze the target.
Time: O(nlogn) +O(n*n) = O(n2)
Space: O(1)

class Solution {
public:    
    /**
     * @param numbers: Give an array numbers of n integer
     * @param target: An integer
     * @return: return the sum of the three integers, the sum closest target.
     */
    int threeSumClosest(vector<int> nums, int target) {
        // write your code here
        if(nums.size() < 3) return INT_MAX;
        int sum = INT_MAX;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 2; i++){
            //int temp_target = target - nums[i];
            int start = i + 1;
            int end = nums.size() - 1;
            while(start < end){
                int temp_sum = nums[i] +nums[start] + nums[end];
                if(abs(temp_sum - target) < abs(sum - target)) sum = temp_sum;
                if(nums[start] + nums[end] == target - nums[i]) return target;
                else if(nums[start] + nums[end] < target - nums[i]){
                    start++;
                }
                else {
                    end--;
                }
            }
        }
        return sum;
    }
};

http://www.cnblogs.com/tenosdoit/p/3649607.html  //参考算法
http://bangbingsyb.blogspot.com/2014/11/leetcode-3sum-closest.html //参考程序



Second Lintcode:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

class Solution { public: /** * @param numbers: Give an array numbers of n integer * @param target: An integer * @return: return the sum of the three integers, the sum closest target. */ int threeSumClosest(vector<int> nums, int target) { //don't need to avoid repetations sort(nums.begin(), nums.end()); if(nums.size() < 3) return 0; int closeSum = nums[0] + nums[1] + nums[2]; for(int i = 0; i < nums.size(); i++){ int start = i + 1; int end = nums.size() - 1; while(start < end){ int tempSum = nums[i] + nums[start] + nums[end]; if(abs(tempSum - target) < abs(closeSum - target)) closeSum = tempSum; if(tempSum < target) start++; else if(tempSum > target) end--; else return target; } } return closeSum; } };