LeetCode 15. 三数之和

Scroll Down

题目

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

 

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

链接:https://leetcode-cn.com/problems/3sum

解答

class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<vector<int>> ans;
		int size = nums.size();
		int p1, p2, p3;
		for (p1 = 0; p1 < size; ++p1) {
			if (p1 > 0 && nums[p1] == nums[p1 - 1]) continue;
			p3 = size - 1;
			int target = -nums[p1];
			for (int p2 = p1 + 1; p2 < size; ++p2) {
				if (p2 > p1 + 1 && nums[p2] == nums[p2 - 1]) continue;
				while (p2<p3 && nums[p2] + nums[p3]>target) p3--;
				if (p2 == p3) break;
				if (nums[p2] + nums[p3] == target) {
					ans.push_back({ nums[p1], nums[p2], nums[p3] });
				}
			}
		}
		return ans;
	}
};