七、三数之和给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。注意答案中不可以包含重复的三元组。暴力起手前先看看题目给的示例。和为0的三元组其实有三个。但是输出要求重复的三元组只能输出一次所以 [-1,0,1] 只能输出一组。明确了题目要求可以面向结果编程了[doge]。三元组说明肯定是三层循环时间复杂度为 O(n³) 起步力扣肯定超时。循环前需要先让数组有序不然这题枚举时间比判断都长几个层级。循环第一遍数组内没有和为 4 的正数组合所以 a 向右移。循环走到这个情况第一组就出来了。找到后继续循环因为要保证不漏掉任何一组正确的三元组所以这里不能打断循环。很快找到了第二组符合要求的。和上一组重复了但是先保留着继续往后找。到这所有符合的答案都找出来了下面进行去重操作。把这些结果扔进 hashset 里让它来完成去重操作。暴力解法基本成型了测试是否符合预期。ps这里有一个小优化target 为正数时永远都不会有符合的三元组所以加一个判断。class Solution { public static ListListInteger threeSum(int[] nums) { ListListInteger mapnew ArrayList(); Arrays.sort(nums); for(int target0;targetnums.length;target){ if(nums[target0]) break; for(int lefttarget1;leftnums.length;left){ for(int rightleft1;rightnums.length;right){ int sumnums[left]nums[right],res-nums[target]; if(sumres ||sumres){ continue; }else{ map.add(new ArrayList(Arrays.asList(nums[target],nums[left],nums[right]))); } } } } return map new ArrayList(new LinkedHashSet(map)); } }和预想的一样代码超时。现在看看如何优化这个代码。咱们重新审视一下这个题它的要求是不是和两数之和有些相似都是找到和为目标值的元素然后返回具体元素只是这题的目标元素是数组内的。不妨尝试一下过了自然好没过再想别的办法。把目标值固定在最左侧两个指针分别指向数组左右两侧。需要找到和为 4 的两个元素不过数组里没有a 右移一格。找到了第一组记录下来继续循环又找到一组。a 继续右移好消息又找到一组。坏消息重复了。这时候就有人抢答了。哎这我熟啊。这不刚讲过嘛。丢进 hashset 处理即可多简单啊。然后就没有然后了。这里还有一种去重处理方法指针移动时判断是否和移动前的元素相同。若相同则继续移动不相同则判断是否符合要求不符合也要 pass 。ps: 不只有 a 要判断三个指针全都要判断循环结束自然就是符合预期的代码。class Solution { public static ListListInteger threeSum(int[] nums) { ListListInteger mapnew ArrayList(); Arrays.sort(nums); for(int a0;anums.length;a){ if(nums[a]0) break; int left a1,rightnums.length-1;int res-nums[a]; int sumnums[left]nums[right]; while(leftright){ if(sumres){ right--; }else if(sumres){ left; }else{ map.add(new ArrayList(Arrays.asList(nums[a],nums[left],nums[right]))); left; right--; while(leftright nums[left]nums[left-1]){ left; } while(leftright nums[right]nums[right1]){ right--; } } } a; while(nums[a]nums[a-1]){ a; } } return map; } }跑测试代码报错了。对于这组数据越界访问。记录唯一一组数据后a 会一直往后移动直到超出数组长度。最外层加上元素判断相同一直跳过跳到越界位置正好跳出整个循环。再次提交测试用例还是会报错。调试一下原因就出来了。a 自增了两次导致每次 left right进不去循环体也没法记录三元组。删掉 for 层自增解决。不要删第二处 a否则 nums[a-1] 会越界优化的完整代码class Solution { public static ListListInteger threeSum(int[] nums) { ListListInteger mapnew ArrayList(); Arrays.sort(nums); for(int a0;anums.length;){ if(nums[a]0) break; int left a1,rightnums.length-1;int res-nums[a]; while(left right){ int sumnums[left]nums[right]; if(sumres){ right--; }else if(sumres){ left; }else { map.add(new ArrayList(Arrays.asList(nums[a], nums[left], nums[right]))); left; right--; while (left right nums[left] nums[left - 1]) { left; } while (left right nums[right] nums[right 1]) { right--; } } } a; while(anums.length nums[a]nums[a-1]){ a; } } return map; } }四数之和细节处理程度不逊色三数之和甚至更甚留到下一篇讲解。