题目：
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: 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] ]
思考：
由于是求三个数的和为0，如果用暴力搜索，则需要O（n^3）的时间，因此这里需要用到很多的技巧，去减少不必要的操作。因此第一步是排序，有序的数组可以使得我们的操作轻松很多；然后进行循环遍历，第一层按顺序遍历整个有序的数组，设数字为i，第二层遍历i之后的整个数组，设数字为j，然后在j之后的数组里面查询是否存在-（i+j），如果存在，则表示这3个数相加为0。
这里可以使用很多的技巧，使得循环可以不完全执行。首先如果i>0，则很明显j和j后面的数组都会大于0，3个大于零的数相加不可能等于0，所以当检索到i > 0时便可以停止整个循环；其次在查询-（i+j）的时候，由于数组有序，可以使用二分查找法，减少搜索时间；使用二分查找法的时候，因为-（i+j）肯定大于0，所以我们可以从0所在的位置开始检索，并且随着i和j的增大，-（i+j）的值将会越来越小，因此上限也可以不断地减少，每次检索成功，我就会把上限定位到上次-（i+j）所在的位置，因此可以也可以减少二分查找的时间。
代码：
#include <algorithm> int binary_search(int find, vector<int>& list1, int low, int high){ int mid = 0; while (low <= high){ mid = (low + high) / 2; if (list1[mid] == find) return mid; else if (list1[mid] > find) high = mid - 1; else low = mid + 1; } return -1; } class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { int size = nums.size(); vector<vector<int>> result_list = vector<vector<int>>(); if (size == 0){ return result_list; } int(*search)(int, vector<int>&, int,int) = binary_search; sort(nums.begin(), nums.end()); int max_ = nums[size - 1]; int zero_pos = search(0, nums, 0, size - 1); int high_pos; int last_i = 100; int last_j; int i, j,pos,t_pos,check; for (i = 0; i < size; i++){ if (nums[i] == last_i) continue; last_i = nums[i]; if (nums[i] > 0) break; last_j = 100; high_pos = size - 1; for (j = i + 1; j < size; j++){ if (nums[j] == last_j) continue; last_j = nums[j]; check = -(nums[i] + nums[j]); if (check > max_) continue; if (check < 0) break; pos = zero_pos > j ? zero_pos : j + 1; t_pos = search(check, nums, pos, high_pos); if (t_pos != -1){ high_pos = t_pos; vector<int> result = vector<int>(); result.push_back(nums[i]); result.push_back(nums[j]); result.push_back(check); result_list.push_back(result); } } } return result_list; } };
结果：
