leetcode15三数之和

题目：

自己的做法：

通过率130 / 318

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		if (nums.empty() || nums.size() < 3) return vector<vector<int>>();
		int num_0 = 0;
		vector<vector<int>> result;
		vector<int> B;
		for (int i = 0; i < nums.size(); i++) {
			if (nums[i] == 0) num_0++;
		}
		if (num_0 == nums.size()) {
			B.push_back(0);
			B.push_back(0);
			B.push_back(0);
			result.push_back(B);
			return result;
		}
		if (nums.size() == 3) {
			int sum = 0;
			for (int i = 0; i < nums.size(); i++) {
				sum += nums[i];
				B.push_back(nums[i]);
			}
			if (sum == 0) {
				result.push_back(B);
				return result;
			}
		}
		quickSort(nums, 0, nums.size() - 1);
		int left = 0, right = 2, i = 1;

		while (i < nums.size()) {
			while (i + 1 < nums.size() && nums[i] == nums[i + 1]) {
				i++;
				left = i - 1;
				right = i + 1;
			}
			if (left < 0 || right >= nums.size()) {
				i++;
				left = i - 1;
				right = i + 1;
				continue;
			}
			int sum = nums[left] + nums[i] + nums[right];
			if (sum < 0) right++;
			else if (sum > 0) left--;
			if (sum == 0) {
				B.push_back(nums[left]);
				B.push_back(nums[i]);
				B.push_back(nums[right]);
				result.push_back(B);
				B.clear();
				//i++;
				while (left - 1 >= 0 && nums[left] == nums[left - 1]) left--;
				while (right + 1 < nums.size() && nums[right] == nums[right + 1]) right++;
				left = left - 1;
				right = right + 1;
			}
		}
		return result;
	}
	void quickSort(vector<int>& arr, int _left, int _right) {
		int left = _left;
		int right = _right;
		int temp = 0;
		if (left < right) {   //待排序的元素至少有两个的情况
			temp = arr[left];  //待排序的第一个元素作为基准元素
			while (left != right) {   //从左右两边交替扫描，直到left = right

				while (right > left&& arr[right] >= temp)
					right--;        //从右往左扫描，找到第一个比基准元素小的元素
				arr[left] = arr[right];  //找到这种元素arr[right]后与arr[left]交换

				while (left < right && arr[left] <= temp)
					left++;         //从左往右扫描，找到第一个比基准元素大的元素
				arr[right] = arr[left];  //找到这种元素arr[left]后，与arr[right]交换

			}
			arr[right] = temp;    //基准元素归位
			quickSort(arr, _left, left - 1);  //对基准元素左边的元素进行递归排序
			quickSort(arr, right + 1, _right);  //对基准元素右边的进行递归排序
		}
	}
};

题解

特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
对数组进行排序。
遍历排序后数组：
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 00，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=n-1，当 L<R 时，执行循环：
当 nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,R 移到下一位置，寻找新的解
若和大于 0，说明 nums[R]太大，R 左移
若和小于 0，说明 nums[L]太小，L 右移

反思

自己的做法是遍历第二个元素开始，left是遍历元素的左边，right是遍历元素的右边。
但是这样出现了很多问题，例如：
遍历的left+i+right和为0之后，再遍历接下来的可能会导致遗漏。

• 题解的做法
  题解是从第一个位置开始left是遍历元素的右边第一个，right是序列最后一个元素。
  同时对于重复元素需要跳过，这样就避免了找不全或者重复找的问题