首先用直觉直觉可以变成两数之和的问题因为nums[i]nums[j]nums[k]0其实也就是-nums[i]nums[j]nums[k]想到两数之和是不够的关键在于想到要把nums排序。排序可以同时解决两件事一是避免重复的三元组二是求两数之和的时候既然是从小到大排列的那么就不用双重循环了可以双指针。class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); Arrays.sort(nums); for(int i0;inums.length-1;i){ //避免重复的三元组措施1 //这一轮不要了比如nums{-8,-8,-8,2,2,3,5,5,6}那么遍历完nums[0]-8以后nums[1]和nums[2]都跳过直接去nums[3]2 if(i0 nums[i]nums[i-1]) continue; twoSum(nums,-nums[i],i1,res); } return res; } /** []nums: 题目传来的原数组 sum两数目标和 start:最左起点 res */ public void twoSum(int []nums, int sum, int start,ListListInteger res){ int small start; int big nums.length-1; //跟快排一样smallbig的时候退出循环 while(smallbig){ if(nums[small]nums[big]sum){ small; while(smallbig nums[small]nums[small-1]){ small; } //small跳过所有重复值此时指向新值。避免重复的三元组措施2 }else if(nums[small]nums[big]sum){ big--; while(smallbig nums[big]nums[big1]){ big--; } //big跳过所有重复值此时big指向新值 }else if(nums[small]nums[big]sum){。避免重复的三元组措施2 ListInteger temp new ArrayList(); temp.add(nums[small]); temp.add(nums[big]); temp.add(nums[start-1]); res.add(temp); //这里让small去走也行让big去走也行我用的small small; while(smallbig nums[small]nums[small-1]){ small; } //small跳过所有重复值此时指向新值。避免重复的三元组措施2 } } } }时间复杂度排序算法时间复杂度O(nlogn)遍历过程中外层循环把nums从左到右遍历一遍内存循环双指针也是线性遍历所以时间复杂度O(n^2)。整个算法的时间复杂度取O(nlogn)和O(n^2) 的最大值所以是O(n^2)。二、暴力解法这个题小白很容易想到暴力解法我们来看看暴力解法。三重循环麻烦在于对于三元组不重复的判断。一开始是下面的写法很垃直接不要看。class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); //把所有可能的两数之和都存进去 for(int i0;inums.length-2;i){ for(int ji1; jnums.length-1;j){ for(int kj1;knums.length;k){ if(nums[i]nums[j]nums[k]0){ //判断和已有的结果不重复才加入 if(!ifExsits(res,nums,i,j,k)){ ListInteger tempnew ArrayList(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); res.add(temp); } } } } } return res; } /** 避免重复三元组 */ public true ifExsits(ListListInteger res, int[] nums,int i,in j,int k){ //笛卡尔积的方式去判断 } }三元组不重复的正确判断方式应该是先给nums排序通过每一次进入循环判断跟上一次的数是否一样一样的话跳出循环这种方式来去重。class Solution { public ListListInteger threeSum(int[] nums) { ListListInteger res new ArrayList(); //排序升序降序都可以--为了三元组去重 Arrays.sort(nums); //把所有可能的两数之和都存进去 for(int i0;inums.length-2;i){ if(i0 nums[i]nums[i-1]) continue; //三元组去重 for(int ji1; jnums.length-1;j){ if(ji1 nums[j]nums[j-1]) continue; //三元组去重 for(int kj1;knums.length;k){ if(kj1 nums[k]nums[k-1]) continue; //三元组去重 if(nums[i]nums[j]nums[k]0){ ListInteger tempnew ArrayList(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); res.add(temp); } } } } return res; } }这种暴力解法会败在时间复杂度上