leetcode题记 15.三数之和

题目

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

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

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

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

来源:力扣(LeetCode)

题解

这道题可以使用遍历+双指针扫描法进行,并加入一定的剪枝优化。

这个办法的精髓在于数组的预处理——排序。排序好了的数组将会对扫描有非常大的帮助。

遍历+双指针扫描

这里有两部分,第一部分是遍历,第二部分是双指针。遍历指的是指遍历一个数作为参照主体。双指针是指以参照主体为参照,对参照主体之后的部分进行一头一尾两个指针向中间扫描。

剪枝

这一套扫描法中,可以有三个位置进行剪枝操作。

剪枝1:

对排序好的数组本身进行分析:
如果数组为:空、个数小于3、第一个数大于0、最后一个数小于0,即代表无法完成三数之和等于0。

剪枝2:

对“遍历”操作进行剪枝:
如果参照主体本身大于0,则代表右侧所有的元素均大于参照主体本身,即为无法完成三数之和大于0,直接结束遍历(break)。

剪枝3:

对“遍历”操作进行剪枝:
如果当前的参照主体与前一个参照主体相等,则代表此参照主体经过相同数组查找出来的“三数之和”结果与之前必定相同,所以可以直接跳过本参照主体(continue)。

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
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ivvec;
int n = nums.size();

// 排序,排序之后的数组会好用很多
sort(nums.begin(), nums.end());

// 剪枝:
// 数组空 || 数字个数小于3 || 排序好的数字第一个大于0 || 排序好的最后一个小于0
if (nums.empty() || n < 3 || nums.front() > 0 || nums.back() < 0) {
return ivvec;
}

for (int i = 0; i < n; ++i) {
int fix = nums[i];

// 剪枝:
// 从大到小排序好的数组,如果扫描进行到了大于0的位置了,那就可以结束了
if (fix > 0)
break;

// 剪枝:
// 如果目前进行的数字与前一个相同,则与之对应的结果必定必定相同
if (i > 0 && fix == nums[i - 1]) continue;

// 双指针法
int l = i + 1, r = n - 1;
while (l < r) {
int sum = nums[l] + nums[r];
if (sum == -fix) {
if (l == i + 1 || r == n - 1) {
ivvec.push_back(vector<int>{fix, nums[l], nums[r]});
++l, --r;
} else if (nums[l] == nums[l - 1]) {
++l;
} else if (nums[r] == nums[r + 1]) {
--r;
} else {
ivvec.push_back(vector<int>{fix, nums[l], nums[r]});
++l, --r;
}
} else if (sum < -fix) {
++l;
} else {
--r;
}
}
}

return ivvec;
}
};

结果

执行用时 : 144 ms, 在所有 C++ 提交中击败了85.23%的用户
内存消耗 : 14.5 MB, 在所有 C++ 提交中击败了95.53%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/07/25/leetcode-15-threeSum/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,