1_相向双指针_leetcode_15_2

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

方法一 穷举搜索 （时间复杂度过高,不展示）

• 时间复杂度:O($n^3$)
• 空间复杂度:$O(1)$

方法二 相向双指针

借助之前1_相向双指针_leetcode_167_1 相向双指针可以将$O(n^2)$的问题下降值$O(n)$,前提是数组有序，所以这题可以先使用快速排是让数组先变得有序，之后使用相向双指针解决。

// C
int cmp(const void *a,const void *b){return *(int*)a - *(int*)b;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {*returnSize = 0;int **ret = (int **)malloc(sizeof(int*) * numsSize * numsSize);*returnColumnSizes = (int *)malloc(sizeof(int)* numsSize * numsSize);qsort(nums,numsSize,sizeof(int),cmp);for(int i = 0;i<numsSize-2;i++){if(i != 0 && nums[i-1] == nums[i]) continue; if(nums[i] + nums[i+1] + nums[i+2] > 0) break;if(nums[numsSize-1]+nums[numsSize-2]+nums[i]<0) continue;int l = i+1;int r = numsSize-1;while(l<r){int sum = nums[l] + nums[r];if(sum > -nums[i]){r--;}else if(sum < -nums[i]){l++;}else{ret[*returnSize] = (int*)malloc(sizeof(int)*3);ret[*returnSize][0] = nums[i];ret[*returnSize][1] = nums[l];ret[*returnSize][2] = nums[r];(*returnColumnSizes)[*returnSize] = 3;r--;l++;(*returnSize)++;while(l<r && nums[l]==nums[l-1]) l++;while(l<r && nums[r]==nums[r+1]) r--;}}}return ret;
}

// C++
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int sum = 0;sort(nums.begin(),nums.end());vector<vector<int>> ret;for(int i = 0;i<nums.size()-2;i++){if(i > 0 && nums[i] == nums[i-1]) continue;if(nums[i] + nums[i + 1] + nums[i+2] > 0) break;if(nums[i] + nums[nums.size()-1] + nums[nums.size()-2] < 0 ) continue;int r = nums.size()-1;int l = i + 1;while(l < r){sum = nums[i] + nums[l] + nums[r];if(sum < 0) l++;else if (sum > 0) r--;else{ret.push_back({nums[i],nums[l],nums[r]});for(l++; l < nums.size() && nums[l]==nums[l-1];l++);for(r--;r > -1 && nums[r]==nums[r+1];r--);}}}return ret;}
};

#python
class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()result = []for i in range(len(nums)-2):if nums[i] + nums[i + 1] + nums[i + 2] > 0: breakif i != 0 and nums[i] == nums[i - 1]: continueif nums[i] + nums[len(nums)-1] + nums[len(nums)-2] < 0: continueleft, right = i+1, len(nums)-1target = -nums[i]while left < right:twoSum = nums[left] + nums[right]if  twoSum > target:right -= 1elif twoSum < target:left += 1else:result.append([nums[i],nums[left],nums[right]])right -= 1left += 1while left < right and nums[left] == nums[left -1]: left += 1while left < right and nums[right] == nums[right+1]: right -= 1return result               

• 时间复杂度:O($n^2$)
• 空间复杂度:$O(logn)$