给定一个有 n 个整数的数组 S,是否存在三个元素 a,b,c 使得 a+b+c=0? 找出该数组中所有不重复的 3 个数,它们的和为 0。
备注:
这三个元素必须是从小到大进行排序。
结果中不能有重复的 3 个数。
例如,给定数组 S={-1 0 1 2 -1 4},一个结果集为:
(-1, 0, 1)
(-1, -1, 2)
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) { sort(nums.begin(), nums.end()); vector<vector<int>> result; int len = nums.size(); for (int current = 0; current < len - 2&&nums[current]<=0;current++) { int front = current + 1, back = len - 1; while (front < back) { if (nums[current] + nums[front] + nums[back] < 0) front++; else if (nums[current] + nums[front] + nums[back] > 0) back--; else { vector<int> v(3); v.push_back(nums[current]); v.push_back(nums[front]); v.push_back(nums[back]); result.push_back(v); v.clear(); do { front++; } while (front < back&&nums[front - 1] == nums[front]); do { back--; } while (front < back&&nums[back + 1] == nums[back]); } } while (current < len - 2 && nums[current + 1] == nums[current]) current++; } return result; } };
继续努力……
和本道题关联密切的题目推荐:
传送门:LeetCode 16 3Sum Closest(最接近的3个数的和)
传送门:LeetCode 18 4Sum(4个数的和)