Halo

A magic place for coding

0%

LeetCode 解题报告(99)-- 15. 3Sum

Problem

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
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]
]

Analysis

   这道题目是非常经典的面试题,题目给定一个数组,然后找到和为 0 的三个数。之前在数组类型题目的题解博客中我也提到过,对于数组类题目很常用的一个做法就是先排序,我们可以利用大小顺序去做文章。这道题目也是一样的,先排序(默认从小到大)。然后我们来看如何满足三个数之和为 0 这个条件,我们把这个表示为 $a + b + c = 0$。那么换一种表达方式就是 $a + b = -c$ 。

   看到后面这种表达方式,就知道前面为什么要排序了。当 $c$ 确定的情况下,如果 $a+b$ 比较大,就要选更小的数,反之就选择更大的数,所以在有序的数组上操作我们就知道要往哪个方向选择。采用双指针的方式,一前一后定位(front 指针和 back 指针),如果 $a+b$ 太小,则增加 **front 指针 **,否则就减小 $back$ 指针。


Solution

   整个过程要保证 front 指针小于 back 指针,同时在匹配上一个三元组之后,需要 skip 掉相同的数字,包括 front 和 back。


Code

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int> > result;
sort (nums.begin (), nums.end ());

int size = nums.size ();
for (int i = 0; i < size; i++) {
if (i > 0 && nums [i] == nums [i - 1]) {
continue;
}
int target = -nums [i];
int front = i + 1;
int back = size - 1;
while (front < back) {
if (nums [front] + nums [back] < target) {
front++;
} else if (nums [front] + nums [back] > target) {
back--;
} else {
vector<int> temp;
temp.push_back (nums [i]);
temp.push_back (nums [front]);
temp.push_back (nums [back]);
result.push_back (temp);

front += 1;
back -= 1;

while (front < back && nums [front] == nums [front - 1]) {
front++;
}
while (front < back && nums [back] == nums [back + 1]) {
back--;
}
}


}
}
return result;
}
};

Summary

   这道题目的难度中等,是面试经常会考到的题目。它首先是一道数组类的题目,所以排序的做法是比较常见的,同时他还考察到了一些数学的知识,通过变换等式来简化程序逻辑。希望这篇博客能够帮助到您,感谢您的支持,欢迎转发、分享、评论,谢谢!

Welcome to my other publishing channels