题解 | #数组中相加和为0的三元组#

数组中相加和为0的三元组

http://www.nowcoder.com/practice/345e2ed5f81d4017bbb8cc6055b0b711

算法思想一：双指针

解题思路

算法流程：

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;
    }
}