暴力解法：三层for循环，每个循环指向一个变量，求所有的和为零的情况

时间复杂度：O(n3)

空间复杂度：O(1)

双指针

1、对数组进行排序

2、外层循环控制第一个数 i；第一个数的范围必须保证小于等于0，若是第一个数大于零，后面的两个数都大于0，不可能实现三数和为零的情况

3、内层循环，控制第二个数 j 的指针初始为 i+1，从前向后遍历；第三个数为最后一个数k

初始为nums.length-1，从后向前遍历。此时计算nums[i]+nums[j]+nums[k]三数之和，将三数之和为0的i、j、k存入集合之中

4、同时存在有相等的数，当存在相同的数时，另一指针先不动，直到相同的数遍历完成为止

时间复杂度：O(n2)

空间复杂度：O(1)

import org.junit.Test;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class ThreeSum {@Testpublic void test() {int[] nums = new int[]{-1, 0, 1, 2, -1, -4};//[-4,-1,-1,0,1,2]int[] nums1 = new int[]{0, 0, 0};for (int i = 0; i < threeSum(nums1).size(); i++) {System.out.println(threeSum(nums1).get(i));//[-1,-1,2],[-1,0,1]}}public static List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);int i = 0;while (nums[i] <= 0 && i <= nums.length - 3) {//小于倒数第二个数int j = i + 1, k = nums.length - 1;while (j < k) {int sum = nums[i] + nums[j] + nums[k];if (sum == 0 && !result.contains(Arrays.asList(nums[i], nums[j], nums[k]))) {result.add(Arrays.asList(nums[i], nums[j], nums[k]));//处理数字相等时的情况//因为最后输出的nums数组中的值，不是索引，所以数字相同可以直接跳过while (j < k && nums[j] == nums[j + 1]) {//j < k避免nums =[0,0,0]的情况下标越界j++;}while (j < k && nums[k] == nums[k - 1]) {k--;}//根据sum的值来调整j和k的位置} else if (sum < 0) {//sum<0说明三数之和较小，需要增大j++;} else {//sum>0说明三数之和较大，需要减小k--;}}i++;}return result;}
}

因为!result.contains(Arrays.asList(nums[i], nums[j], nums[k]))的判断在数据量大的时候判断相当占用时间，因此数据量大的时候会报超时

要想在不进行判断是否能够被存入数组，就需要保证在遍历的时候跳过i、j、k三个指针所有指向的相同的数据。因此All Perfect代码对第一、二、三个数都排除了相同数据的情况

反之，可以得出，在不排除相同的数据时，对于每一组数在进入集合前，都需要判断是否能够被存入集合。但contains一多整个代码跑的就慢

All Perfect代码

class Solution {public List<List<Integer>> threeSum1(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length; i++) {//第一个数iif (nums[i] > 0) {//大于0时退出循环break;}if (i > 0 && nums[i] == nums[i - 1]) {//如果相同，直接执行下一个//因为最后输出的nums数组中的值，不是索引，所以数字相同可以直接跳过continue;}int l = i + 1, r = nums.length - 1;while (l < r) {int sum = nums[i] + nums[l] + nums[r];if (sum == 0) {res.add(Arrays.asList(nums[i], nums[l], nums[r]));//处理相同的数的情况//因为最后输出的nums数组中的值，不是索引，所以数字相同可以直接跳过while (l < r && nums[l] == nums[++l]) ;while (l < r && nums[r] == nums[--r]) ;} else if (sum < 0) {l++;} else {r--;}}}return res;}
}