leetcode 15 3Sum

Question：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)

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    }

这种类型的题目都是一样的，KSum 也只需先排序，然后确定k－2个数，剩下两个数进行夹逼。注意为了跳过重复的三元组所作的努力。

1.夹逼的实现##

    while (j<k) {//!!!!!!!!!!!!!!!夹逼
                if(*i + *j + *k < 0)
                {
                    j++;
                    while ( j<k && *j == *(j-1) ) j++;
                }
                else if(*i + *j + *k > 0)
                {
                    k--;
                    while ( j<k && *k == *(k+1) ) k--;
                }
                else
                {
                    result.push_back({*i, *j, *k});
                    j++;
                    k--;
                    while (*j==*(j-1) && *k==*(k+1) && j<k )j++;//!!!!!!!!!!这么做是为了不重复，只改一边是因为可能不能同时改两边
                }

2.代码##

//
//  main.cpp
//  leetcode
//
//  Created by YangKi on 15/11/11.
//  Copyright © 2015年 YangKi. All rights reserved.
//

#include<cstdlib>
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>result;
        int size=nums.size();
        if(size<3) return result;
        sort(nums.begin(), nums.end());
        
        auto last=nums.end();
        
        for ( auto i=nums.begin(); i<last-2; i++ ) {
            if( i>nums.begin() && *i==*(i-1) )//注意：i只需放在每种数的第一个位子，后面的位子不用再放，
                                              //因为在第一个位子得到的种类肯定比放后面的多，而且这样做可以防止得到重复的三元组
            {
                continue;
            }
            
            auto j=i+1;
            auto k=last-1;
            
            while (j<k) {//!!!!!!!!!!!!!!!夹逼
                if(*i + *j + *k < 0)
                {
                    j++;
                    while ( j<k && *j == *(j-1) ) j++;
                }
                else if(*i + *j + *k > 0)
                {
                    k--;
                    while ( j<k && *k == *(k+1) ) k--;
                }
                else
                {
                    result.push_back({*i, *j, *k});
                    j++;
                    k--;
                    while (*j==*(j-1) && *k==*(k+1) && j<k )j++;//!!!!!!!!!!这么做是为了不重复，只改一边是因为可能不能同时改两边
                }
            }
            
        }
        
        return result;
        
    }
};

int main()
{
    Solution *s=new Solution();
    
    return 0;
}