3Sum&&3Sum Closest

首先给出题目，这两题都是感觉有点儿复杂，但是道理是相通的题目。

3Sum

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

3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

假如是2Sum，那么很简单，首先进行一次排序，然后不断的移动首尾指针，当首尾指针和大于0，则移动右指针，反之移动左指针，很好理解。但是在3个数字的情况下，的确有点儿复杂了。

直接讲思路，我们也将数组进行排序，然后不断的遍历每个数字，把该数字当做3个数字之中的第一个，那么剩下两个数字，我们就从它之后取。这样我们就把该题化为了2Sum的题目了。至于剩下两个数字的和是多少，则在3Sum这题中，则是第一个数字的相反数，而另外一题中，则是target减去第一个数字的值，其余的处理方法是一样的。

在3sum closest中，我们得记下与target最接近的值，然后返回它。下面贴出两个题目的解法：

class ThreeSum {
public:
    static void test() {
        vector<int> nums;
        int na[] = {-1,0,1,2,-1,-4};
        for (int i = 0; i < sizeof(na) / sizeof(na[0]); i++) {
            nums.push_back(na[i]);
        }
        auto ret = threeSum(nums);
    }

    static vector<vector<int>> threeSum(vector<int>& nums) {
        if (nums.size() < 3) {
            return vector<vector<int>>();
        }
        vector<vector<int>> res;
        vector<int> pos;
        std::sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; i++) {
            if (nums[i] > 0) {
                break;
            }
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            int fnum = -1 * nums[i];
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[l] + nums[r];
                bool ml = false, mr = false;
                if (sum == fnum) {
                    pos.push_back(nums[i]);
                    pos.push_back(nums[l]);
                    pos.push_back(nums[r]);
                    res.push_back(std::move(pos));
                    ml = true; mr = true;
                } else if (sum > fnum) {
                    mr = true;
                } else {
                    ml = true;
                }
                if (mr) {
                    int pv = nums[r];
                    while (r > l) {
                        if (nums[r] != pv) {
                            break;
                        }
                        r--;
                    }
                }
                if (ml) {
                    int pv = nums[l];
                    while (r > l) {
                        if (nums[l] != pv) {
                            break;
                        }
                        l++;
                    }
                }
            }
        }
        return res;
    }
};

class ThreeSumClosest {
public:
    static void test() {
        vector<int> nums;
        int na[] = {0, 2, 1, -3};
        for (int i = 0; i < sizeof(na) / sizeof(na[0]); i++) {
            nums.push_back(na[i]);
        }
        auto ret = threeSumClosest(nums, 1);
    }

    static int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3) {
            return 0;
        }
        int *mt = nullptr;
        std::sort(nums.begin(), nums.end());
        bool lt = false;
        for (int i = 0; i < nums.size() - 2; i++) {
            if (nums[i] > target) {
                if (lt) {
                    break;
                }
                lt = true;
            }
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            int fnum = target - nums[i];
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[l] + nums[r];
                int nt = sum + nums[i];
                if (mt == nullptr || abs(nt - target) < abs(*mt - target)) {
                    if (nullptr == mt) {
                        mt = new int;
                    }
                    *mt = nt;
                }
                bool ml = false, mr = false;
                if (sum == fnum) {
                    return target;
                } else if (sum > fnum) {
                    mr = true;
                } else {
                    ml = true;
                }
                if (mr) {
                    int pv = nums[r];
                    while (r > l) {
                        if (nums[r] != pv) {
                            break;
                        }
                        r--;
                    }
                }
                if (ml) {
                    int pv = nums[l];
                    while (r > l) {
                        if (nums[l] != pv) {
                            break;
                        }
                        l++;
                    }
                }
            }
        }
        int res = *mt;
        delete mt;
        return res;
    }
};