15、LeetCode 题解 - 3 Sum（3 个数的和）
2019-07-10
目录
- > 1、/null - LeetCode 题解 - Two Sum
- > 2、/null - LeetCode 题解 - Add Two Numbers
- > 3、/null - LeetCode 题解 - Longest Substring Without Repeating Characters
- > 4、/null - LeetCode 题解 - Longest Palindromic Substring（最大回文子字符串）
- > 5、/null - LeetCode 题解 - ZigZag Conversion（Z型转换）
- > 6、/null - LeetCode 题解 - Reverse Integer（翻转整数）
- > 7、/null - LeetCode 题解 - String to Integer (atoi)（转换到整型）
- > 8、/null - LeetCode 题解 - String to Integer (atoi)（转换到整型）
- > 9、/null - LeetCode 题解 - Palindrome Number（回文数）
- > 10、/null - LeetCode 题解 - Regular Expression Matching （正则表达式匹配）
- > 11、/null - LeetCode 题解 - Container With Most Water（最大水容器）
- > 12、/null - LeetCode 题解 - Integer to Roman（整型数到罗马数）
- > 13、/null - LeetCode 题解 - Roman to Integer（罗马数到整型数）
- > 14、/null - LeetCode 题解 - Longest Common Prefix（最长公共前缀）
- > 15、/null - LeetCode 题解 - 3 Sum（3 个数的和）
- > 16、/null - LeetCode 题解 - 3 Sum Closest（最接近的 3 个数的和）
- > 17、/null - LeetCode 题解 - Letter Combinations of a Phone Number（电话号码的字母组合）
- > 18、/null - LeetCode 题解 - 4 Sum（4 个数的和）
- > 19、/null - LeetCode 题解 - Remove Nth Node From End of List（从列表尾部删除第 N 个结点）
- > 20、/null - LeetCode 题解 - Valid Parentheses（有效的括号）
- > 21、/null - LeetCode 题解 - Merge Two Sorted Lists（合并两个已排序的数组）
- > 22、/null - LeetCode 题解 - Generate Parentheses（生成括号）
- > 23、/null - LeetCode 题解 - Merge k Sorted Lists（合并 K 个已排序链表）
- > 24、/null - LeetCode 题解 - Swap Nodes in Pairs（交换序列中的结点）
- > 25、/null - LeetCode 题解 - Reverse Nodes in k-Group（在K组链表中反转结点）
- > 26、/null - LeetCode 题解 - Remove Duplicates from Sorted Array（从已排序数组中移除重复元素）
- > 27、/null - LeetCode 题解 - Implement strStr()（实现 strStr() 函数）
翻译
给定一个有 n 个整数的数组 S，是否存在三个元素 a,b,c 使得 a+b+c=0? 找出该数组中所有不重复的 3 个数，它们的和为 0。
备注：
这三个元素必须是从小到大进行排序。
结果中不能有重复的 3 个数。
例如，给定数组 S={-1 0 1 2 -1 4}，一个结果集为：
(-1, 0, 1)
(-1, -1, 2)
原文
Given an array S of n integers,
are there elements a, b, c in S such that a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order.
(ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
经典方法，可惜我并没有想到这样写……
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int len = nums.size();
for (int current = 0; current < len - 2&&nums[current]<=0;current++)
{
int front = current + 1, back = len - 1;
while (front < back)
{
if (nums[current] + nums[front] + nums[back] < 0)
front++;
else if (nums[current] + nums[front] + nums[back] > 0)
back--;
else
{
vector<int> v(3);
v.push_back(nums[current]);
v.push_back(nums[front]);
v.push_back(nums[back]);
result.push_back(v);
v.clear();
do {
front++;
} while (front < back&&nums[front - 1] == nums[front]);
do {
back--;
} while (front < back&&nums[back + 1] == nums[back]);
}
}
while (current < len - 2 && nums[current + 1] == nums[current])
current++;
}
return result;
}
};
继续努力……
和本道题关联密切的题目推荐：
传送门：LeetCode 16 3Sum Closest（最接近的3个数的和）
传送门：LeetCode 18 4Sum（4个数的和）
