15.三数之和

三数之和

排序 + 双指针

1. 排序
2. 一个循环，确定三个数中的一个
3. 使用双指针，如果三数之和大于0，右指针左移（因为由小到大排序，所以左边的数要小于右边）

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    sort(nums.begin(), nums.end()); // 序
    if (nums.size() < 3) return ans; // 果不够三个数直接返回
    for (int i = 0; i < nums.size() - 2; i++) { //先确定其中一个数
        while (i && i < nums.size() && nums[i] == nums[i-1]) i++; // 重，重复数字跳过
        int l = i+1, r = nums.size() - 1; //两个指针 l 和 r
        while (l < r) {
            int sum = nums[l] + nums[r] + nums[i]; //得到三数之和
            if (sum > 0) r--; // 如果大于零 左移
            else if (sum < 0) l ++; // 如果小于零 右移
            else { // 等于
                ans.push_back({nums[i], nums[l], nums[r]}); // 添加进答案
                l++, r--;
                while (l < nums.size() && nums[l] == nums[l-1]) l++; // 判重
                while (r > 0 && nums[r+1] == nums[r]) r--;
            }
        }
    }
	return ans;
}