15. 3Sum

Description

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.
Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution

1. Two Sum求的是数组中两数之和=target的下标，并且题目保证了结果的唯一性；本题求三数之和=0，所以可以先排序，在一层遍历里使用双向夹逼来求解，最终的时间复杂度O(n*logn) + O(n²) = O(n²)，保证结果的不重复是关键，也可以借助set保证结果不重复

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int> > ret;
    if (nums.size() < 3) {
        return ret;
    }
    sort(nums.begin(), nums.end());

    for (int i = 0; i < nums.size() - 2; ++i) {
        int begin = i + 1, end = nums.size() - 1, target = -nums[i];
        if (target < 0) {//提前剪枝，如果nums[i]>0，肯定不可能存在两个比nums[i]还大的数，三者之和=0
            break;
        } else if (i > 0 && nums[i] == nums[i - 1]) {//数值相等直接跳过，否则会导致重复结果
            continue;
        }
        while (begin < end) {
            if (nums[begin] + nums[end] < target) {
                begin++;
            } else if (nums[begin] + nums[end] > target) {
                end--;
            } else {
                vector<int> curItem = {nums[i], nums[begin], nums[end]};
                ret.push_back(curItem);
                while (begin < end && nums[begin] == nums[begin + 1]) {//下同，防止出现重复结果
                    begin++;
                }
                while (end > begin && nums[end] == nums[end - 1]) {
                    end--;
                }
                begin++;
                end--;
            }
        }
    }
    return ret;
}