# 引言
题目链接：https://leetcode.com/problems/3sum/description/
# 题目大意
给出一个包含 n 个整数的数组 nums, 这个数组是否存在元素有 a,b,c 使得 a + b + c = 0 , 找出所有满足条件的 a,b,c 的组合
- Example
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
# 题解
很容易想到暴力解法，三重循环穷举所有可能进行判断，但很明显这种方法会超时，想一想有什么办法能够优化不必要的循环？
排序？
将数组排序，从起始点进行大小长度为三的滚动判断即可，这样就好像省去了两重循环，事件复杂度变成了 O (3*n)?
由于数字可能为负数，所以选取当前有序数组两端的数字更可能构成目标数字零，所以数字的滚动不应该选取连续的。
选择一个标志点作为第一个数字从零开始往后推进，从当前标志位往后剩余数组两端选取剩余两个目标数字进行判断，并不断往中间压缩判断即可 (由于数组有序，剩余两个数在当前位置之后寻找，只要第一个数字不断推进直到结束，过程中可以覆盖所有解)
具体压缩判断条件如下：
每次根据当前选取三个数字的和和目标值 0 比较，大于目标值 0, 第三个数字从剩余数组从后往前选取，小于目标值 0, 第二个数字从剩余数组从前往后选取，每次选定三个目标值后将数字的和和目标值 0 比较，满足条件存储即可
int midIndex = i + 1;
int lastIndex = len - 1;
int curSum = nums[i] + nums[midIndex] + nums[lastIndex];
if (curSum > 0) --lastIndex;
if (curSum < 0) ++midIndex;
# 复杂度
时间复杂度 O(n^2)
空间复杂度 O(1)
# AC 代码
c++ 版本
class Solution | |
{ | |
public: | |
vector<vector<int>> threeSum(vector<int> &nums) | |
{ | |
vector<vector<int>> retAns; | |
std::sort(nums.begin(), nums.end()); | |
const int len = nums.size(); | |
for (int i = 0; i < len - 2; ++i) | |
{ | |
if (nums[i] > 0) | |
{ | |
break; | |
} | |
if (i > 0 && nums[i] == nums[i - 1]) | |
{ | |
continue; | |
} | |
int midIndex = i + 1; | |
int lastIndex = len - 1; | |
while (midIndex < lastIndex) | |
{ | |
int curSum = nums[i] + nums[midIndex] + nums[lastIndex]; | |
if (curSum == 0) | |
{ | |
retAns.push_back({nums[i], nums[midIndex++], nums[lastIndex--]}); | |
while (midIndex < lastIndex && nums[midIndex] == nums[midIndex - 1]) | |
{ | |
++midIndex; | |
} | |
while (midIndex < lastIndex && nums[lastIndex] == nums[lastIndex + 1]) | |
{ | |
--lastIndex; | |
} | |
} | |
else if (curSum > 0) | |
{ | |
--lastIndex; | |
} | |
else | |
{ | |
++midIndex; | |
} | |
} | |
} | |
return retAns; | |
} | |
}; |
go 版本
func threeSum(nums []int) [][]int { | |
var retAns [][]int | |
lens := len(nums) | |
sort.Sort(sort.IntSlice(nums)) | |
for i := 0; i < lens-2; i++ { | |
if nums[i] > 0 { | |
break | |
} | |
if i > 0 && nums[i] == nums[i-1] { | |
continue | |
} | |
midIndex, lastIndex := i+1, lens-1 | |
for midIndex < lastIndex { | |
curSum := nums[i] + nums[midIndex] + nums[lastIndex] | |
if curSum == 0 { | |
retAns = append(retAns, []int{nums[i], nums[midIndex], nums[lastIndex]}) | |
midIndex++ | |
for midIndex < lastIndex && nums[midIndex] == nums[midIndex-1] { | |
midIndex++ | |
} | |
lastIndex-- | |
for midIndex < lastIndex && nums[lastIndex] == nums[lastIndex+1] { | |
lastIndex-- | |
} | |
} else if curSum > 0 { | |
lastIndex-- | |
} else { | |
midIndex++ | |
} | |
} | |
} | |
return retAns | |
} |
