题目链接
题目描述
给你 n 个整数的数组 nums,判断是否存在三个元素 a,b,c ,
使得 a + b + c = 0 ?
请你找出所有和为 0 且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
思路
-
假设不是找三个元素,而是两个元素。
首先要确定一个元素,至少要把所有元素遍历一遍,是O(n)。
其次,找到另一个符合的元素的最优复杂度是O(logn),合起来的复杂度是O(nlogn)。
关键是如何避免重复,可以先把数组排序,确定第一个元素时,遇到重复的直接跳过。
第一个元素不重复,那么找到的第二个元素一定也不重复。 -
那么考虑三个元素时,排序+双指针。
从后往前遍历。
若 nums[i]>0,因已排序,后面不可能有三个数加和等于0,直接返回结果。
对于重复元素:跳过,避免出现重复解。
令左指针为L=i+1,右指针R=n-1,当 L<R 时,执行循环:
当 nums[i]+nums[L]+nums[R]==0,记录答案,并更新左指针,同时判断是否重复。
若和大于 0,说明 nums[R]太大,R 左移
若和小于 0,说明 nums[L]太小,L 右移
时间复杂度为O(n^2)
C++方法
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int pL, pR, T, L, R;
int len = nums.size();
vector<vector<int>> ans;
for (int i = 0; i < len; i++) {
if (i != 0 && nums[i] == nums[i-1])
continue;
T = nums[i];
if (T > 0)
break;
pL = i+1, pR = len-1;
while(pL < pR) {
L = nums[pL], R = nums[pR];
if (T+L+R == 0) {
ans.push_back({L,T,R});
pL ++;
while (pL<pR && nums[pL-1] == nums[pL])
pL++;
}
else if (T+L+R < 0)
pL ++;
else if (T+L+R > 0)
pR --;
}
}
return ans;
}
};