算法思想一:双指针

解题思路

算法流程:
1、特判,对于数组长度 n,如果数组为 null 或者数组长度小于 3,返回 []。
2、对数组进行排序。
3、遍历排序后数组:
    1、若 num[i]>0:因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回结果。
    2、对于重复元素:跳过,避免出现重复解
    3、令左指针 L=i+1,右指针R=n−1,当 L<r 时=""> </r>
        1、当 nums[i]+nums[L]+nums[R]==0,执行循环,判断左界和右界是否和下一位置重复,去除重复解。并同时将 L,R移到下一位置,寻找新的解
        2、若和大于 0,说明 nums[R] 太大,R 左移
        3、若和小于 0,说明 nums[L] 太小,L 右移
图解:

代码展示:

Python版本
class Solution:
    def threeSum(self , num ):
        # write code here
        n=len(num)
        res=[]
        if(not num&nbs***bsp;n<3): return [] num.sort() res=[] for i in range(n): if(num[i]>0):
                return res
            if(i>0 and num[i]==num[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<r>0):
                    R=R-1
                else:
                    L=L+1
        return res</r>
JAVA版本
import java.util.*;
public class Solution {
    public ArrayList threeSum(int[] num) {
        ArrayList ret = new ArrayList<>();
        if(num==null || num.length<3) { return ret; } Arrays.sort(num); for(int i=0;i<num.length-2>0)
            {
                return ret;
            }
            if(i>0 && num[i]==num[i-1])
                continue;
            int L = i+1;
            int R = num.length-1;
            while(L<r>();
                    list.add(num[i]);
                    list.add(num[L]);
                    list.add(num[R]);
                    ret.add(list);
                    
                    while(L<r>0){
                    R--;
                }
                else if(sum<0){ L++; } } } return ret; } }</r></r></num.length-2>

复杂度分析

时间复杂度O(N^2):N表示数组的长度,数组排序 O(NlogN),遍历数组 O(n),双指针遍历 O(n),总体 O(NlogN)+O(n)∗O(n),O(N^2)
空间复杂度O(1):仅使用指针等常数级变量空间

算法思想二:暴力循环法

解题思路

1、正常情况下按照三重暴力循环可以解决该问题
2、因为题目要求不准出现重复的三元组,所以我们可以先将数组排个序,每次遍历时有 num[i] != num[i-1]、num[j] != num[j-1]、num[k] != num[k-1]
3、当固定 i 的值时,有 j + k = -i ,当 j 越大, k 就会越小,所以可以将 k 从后往前遍历,当 j 往后遍历时, k 就往前遍历。

代码展示:

JAVA版本
import java.util.*;
public class Solution {
    public ArrayList threeSum(int[] num) {
        // 排序
        Arrays.sort(num);
        ArrayList list = new ArrayList<>();
        // 暴力双重循环
        for (int i = 0; i < num.length - 2; ++i) { // 去除重复 if (i != 0 && num[i - 1] == num[i]) continue; // 定义k指针 int k = num.length - 1; for (int j = i + 1; j < num.length - 1; ++j) { // 去除重复 if (j != i + 1 && num[j] == num[j - 1]) continue; while (j < k && num[i] + num[j] + num[k] > 0) --k;
                if (j == k) break;
                if (num[i] + num[j] + num[k] == 0) {
                    // 添加子解
                    ArrayListele = new ArrayList<>();
                    ele.add(num[i]);
                    ele.add(num[j]);
                    ele.add(num[k]);
                    list.add(ele);
                }
            }
        }
        return list;
    }
}

复杂度分析

时间复杂度O(N^2):N表示数组的长度,变量 i 一重循环,j k 依次循环遍历
空间复杂度O(1):额外空间变量 i j k为o(1),ele 固定空间数也为o(1)