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: break
            if i != 0 and nums[i] == nums[i - 1]: continue
            if nums[i] + nums[len(nums)-1] + nums[len(nums)-2] < 0: continue
            left, right = i+1, len(nums)-1
            target = -nums[i]
            while left < right:
                twoSum = nums[left] + nums[right]
                if  twoSum > target:
                    right -= 1
                elif twoSum < target:
                    left += 1
                else:
                    result.append([nums[i],nums[left],nums[right]])
                    right -= 1
                    left += 1
                    while left < right and nums[left] == nums[left -1]: left += 1
                    while left < right and nums[right] == nums[right+1]: right -= 1
                    
        return result               

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