前几天偶尔看到一道题，感觉蛮有意思的，在自己思考，外加上网查询之后，找到了一个比较完美的算法解决。问题描述如下：
给定有序排列的N个整数，找出其中3个数相加和为0，输出所有的不重复的3个数，要求输出的结果依然有序。
在单行内，输出的顺序和原来一致，每行之间的顺序和第一个数字在原数列中的顺序一致（如果相同则向后依次比较）
INPUT :
5
-2 -1 0 1 2
OUTPUT:
-2 0 2
-1 0 1
INPUT :
5
2 2 0 -2 -4
OUTPUT:
2 2 -4
2 0 -2
思路
首先思考：寻找有序数组（下文说的数组均是升序排列的）中两个和为 k 的值。很简单，两个指针 i 和 j 分别指向数组两端，计算两数的和，大于 k 则 j--，否则 i++，直到寻找到两个数和为 k 或者 i > j 时停止。
上题中可以转换为寻找数组中两个和为 -k 的数，k 为数组中的元素，我们只需要再加一层循环，遍历数组中的值，作为 k 就可以了。
那么如何解决结果中有重复值的情况呢？比如我们输入 [-4, -2, 0, 2, 2] 这5个数，会输出两次 [-2, 0, 2]。其实这个也很好判断，当我们确定了三个数中的一个数，那么后面求出的两个数就确定下来了，比如我们确定”第一个数”是 -5，那么可能求出后面两个数是 [2, 3] 和 [1, 4]，当我们循环到下一个”第一个数”的时候，如果还是 -5，那求出的数据肯定还是重复的，所以直接跳过就好。【这块的描述好像不是很清楚啊！(╯‵□′)╯︵┻━┻ 不明白的话看下面的代码肯定一下子就明白了呢！】
代码实现
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
55
56
57
58
59
60
61
62
63
| #include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> findThreeNumber(vector<int> arr, bool asc) {
int size = arr.size();
vector<vector<int>> result;
for (int i = 0; i < size; i++) {
int m = i + 1;
int n = size - 1;
while (m < n) {
int sum = arr[m] + arr[n];
if (sum + arr[i] > 0) {
asc ? n-- : m++;
}
else if (sum + arr[i] < 0) {
asc ? m++ : n--;
}
else {
vector<int> v(3);
v[0] = arr[i];
v[1] = arr[m];
v[2] = arr[n];
result.push_back(v);
do {
m++;
} while (m < n && arr[m - 1] == arr[m]);
do {
n--;
} while (m < n && arr[n + 1] == arr[n]);
}
}
while (i < size - 2 && arr[i + 1] == arr[i]) {
i++;
}
}
return result;
}
int main() {
bool asc = true;
int n = 0;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
if (i > 0 && arr[i] < arr[i - 1]) {
asc = false;
}
}
vector<vector<int>> result = findThreeNumber(arr, asc);
for each (vector<int> v in result) {
cout << v[0] << " " << v[1] << " " << v[2] << endl;
}
system("pause");
}
|
文章标题：找出有序数组中 3 个和为 0 的数
文章作者：cylong
文章链接：https://0skyu.cn/posts/c16b.html
有问题或者建议欢迎在下方评论。欢迎转载、引用，但希望标明出处，感激不尽(●’◡’●)
