LeetCode 15 3Sum 解题日志

LeetCode 15原题如下：

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:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• 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)

   题意为：在一个数组中，寻找三个数之和为0的所有组合，要求三个数有非递减的特性，并且最后求出解集没有重复。
   此题的暴力解法即为尝试所有组合，三层for循环，并排除掉重复的解集，时间复杂度是O(n^3）。
   由于需要求和，可以考虑先对数组排序，有序的数据肯定有利于寻找求和的数。
   排序后，按照顺序依次取出数组里面的数，然后在剩余的数中，找出两个数之和与这个数为相反数；对于有序的数组，可以排除掉相同的数据。
   这样也达到了排除重复的解集的目的。
   代码如下：

class Solution {
public:

    vector<vector<int>> result;
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        int len = nums.size();

        for (size_t i = 0; i < nums.size(); i++)
        {
            if (i>0 && nums[i] == nums[i - 1])//去除重复的值//
            {
                continue;
            }

            find(nums, i + 1, len - 1, nums[i]);

        }


        return result;
    }

    void find(vector<int> &nums, int start, int end, int target)
    {
        vector<int> temp(3,0);
        while (start < end)
        {
            int sum = nums[start] + nums[end] + target;
            if (sum == 0)
            {
                temp[0]=target;
                temp[1]=nums[start];
                temp[2]=nums[end];

                result.push_back(temp);
                while (start < end&&nums[start] == nums[start + 1]) //跳过重复的值//
                {
                    start++;
                }
                while (start < end&&nums[end] == nums[end - 1])//跳过重复的值//
                {
                    end--;
                }
                start++;
                end--;
            }
            else if (sum < 0)
            {
                start++;
            }
            else
            {
                end--;
            }
        }
    }
};