Leetcode-15 3Sum

发表于 | 分类于 | 次

3Sum

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example 1

1
2
3
4
5
6
7
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解题思路

三指针法。当数组元素均为正数或均为负数时，不可能有 a+b+c==0。因此可将数组排序，以判断数组元素是否均为正数或负数，并方便采用双指针解决 2Sum: a+b=-c 的问题。在外层循环选定 target，在内层循环使双指针靠近。若其和为 target，将该合法“三数”加入结果集，若其和小于 target，递增左指针，否则递减右指针。为避免重复，在外层循环跳过被考虑过的 target，在内层循环跳过相同元素。

复杂度分析

  • 时间复杂度：$O(n^2)$。
  • 空间复杂度：$O(1)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		vector<vector<int>> res;
		sort(nums.begin(), nums.end());
		if (nums.empty() || nums.front() > 0 || nums.back() < 0)
			return res;
		for (int i = 0; i < nums.size(); ++i) {
			if (nums[i] > 0) return res;
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			int target = -nums[i];
			int j = i + 1, k = nums.size() - 1;
			while (j < k) {
				if (nums[j] + nums[k] == target) {
					res.push_back({ -target,nums[j],nums[k] });
					while (j < k&&nums[j + 1] == nums[j])++j;
					while (j < k&&nums[k - 1] == nums[k])--k;
					++j;
					--k;
				}
				else if (nums[j] + nums[k] < target)
					++j;
				else --k;
			}
		}
		return res;
	}
};