三数之和

问题描述：

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
本题需要注意：1、三个元素a+b+c=0
2、vector内可能存在重复元素，但是返回结果中不允许重复

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

思路：

1、找到a+b+c=0的组合
首先，对vector进行排序。
三个数之中必须存在至少一个小于0的数，否则无法保证三个数的和为0；
第一个数a从0到n-2遍历（因为vector已经从大到小排序，所以必须保证a<0）；第二个数b从a的下一个位置first开始；第三个数c从n-1开始。
如果a+b+c<0,b太小，所以first向后移，first++；如果a+b+c>0,c太大，所以last向前移，last--；否则，将a、b、c插入到vec中。
在first和last移动的过程中，必须保证first<last;
2、在这过程中可能会出现重复->去重
每次在进行操作的时候只取相同的数较左边的那个(右边的相同数字，跳过即可)。

题解：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &nums) {
        vector<int> B;
        vector<vector<int>> A;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int first;
        int last;
        for (int i = 0; i < n - 2 && nums[i] <= 0; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            first = i + 1;
            last = n - 1;
            while (first < last) {
                if (nums[i] + nums[first] + nums[last] > 0) {
                    last--;
                } else if (nums[i] + nums[first] + nums[last] < 0) {
                    first++;
                } else {
                    B.push_back(nums[i]);
                    B.push_back(nums[first]);
                    B.push_back(nums[last]);
                    A.push_back(B);
                    B.clear();
                    first++;
                    while (first < last && nums[first] == nums[first - 1]) {
                        first++;
                    }
                }
            }

        }
        return A;
    }
};