问题

        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-当前的数组用两个指针分别指向剩余数组的第一个位置和最后一个位置，判断： 相等，记录，将start和end指针分别向后和向前移动，直到到达位置的元素与当前的start和end不想等（主要用于去除相同的结果）大于，end前移小于，start后移 -

解答

std::vector<std::vector<int>> threeSum(std::vector<int>& nums){ std::vector<std::vector<int>> result; if (nums.size() <= 2) return result; sort(nums.begin(), nums.end()); for (std::vector<int>::iterator i = nums.begin(); i < nums.end(); i++){ int target = 0 - *i; std::vector<int>::iterator start = i+1; std::vector<int>::iterator end = nums.end()-1; if (i!=nums.begin()&&*(i-1) == *i){ continue; } while (start < end){ if (*start + *end == target){ std::vector<int> tmp; tmp.push_back(*i); tmp.push_back(*start); tmp.push_back(*end); result.push_back(tmp); while (*(start)==*(start+1)&&start<end) start++; start++; while (*(end) == *(end-1) && start<end) end--; end--; } else if (*start + *end > target){ end--; } else{ start++; } } } return result; }