学步园

蛮常见一道题目。

思路：

1：排序，按顺序遍历两个数之和twoSum，

2： 二分查找 （0 - twoSum)看是否存在

这题最容易错的地方是must not contain duplicate triplets，所以遍历的这时候要用一个数字记录最后一个遍历的数字是，避免重复。

#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;


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

		vector<vector<int>> combs;
		if (num.size() < 3)
			return combs;

		sort(num.begin(), num.end());
		int prei;
		for (int i = 0; i < num.size() - 2; i++)
		{
			if (i > 0 && num[i] == num[prei])
				continue;
			if (num[i]>0)
				break;

			int prej;
			for (int j = i + 1; j < num.size() - 1; j++)
			{
				if (j > i + 1 && num[j] == num[prej])
					continue;

				int twoSum = num[i] + num[j];
				int value = 0 - twoSum;

				if (value >= num[j + 1] && value <= num.back())
				{
					bool flag = searchValue(num, j + 1, num.size() - 1, value);
					if (flag == true){
						vector<int> comb;
						comb.push_back(num[i]);
						comb.push_back(num[j]);
						comb.push_back(value);
						combs.push_back(comb);
					}
				}
				prej = j;
			}

			prei = i;

		}

		return combs;
	}

	bool searchValue(vector<int> num, int left, int right, int value)
	{
		while (left <= right){
			int m = (left + right) / 2;

			if (num[m] == value)
				return true;
			else if (num[m] < value)
				left = m + 1;
			else
				right = m - 1;
		}
		return false;
	}
};