卷进大厂系列之LeetCode刷题笔记：三数之和（中等）

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []输出：[]

示例 3：

输入：nums = [0]输出：[]

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

涉及知识点

这是一道中等难度题目，但是思路是比较简单的。首先想到的还是暴力解法，但很明显三次for循环的暴力解法是超时的，其时间复杂度为O(n³)。不过思路是正确的，我们可以对此进行优化，降低其时间复杂度。第一种方法是使用哈希表法，即先排序，接着使用两个for循环，求出其中两个元素的和，然后剩下的一个一个元素使用哈希表来判断是否有这个值（注意去重）；第二种方法是双指针法，即首先对数组排序，然后利用双指针的移动来找出满足条件的值。

根据上面分析，我们需要了解的知识点如下：

• 数组是存储在连续内存空间的相同类型数据的集合
• 数组下标都是从0开始
• 数组在内存空间的地址都是连续的
• 数组是一个简单的哈希表，其中哈希表中的关键码就是数组的索引下标
• 哈希表可以根据关键码直接访问数据
• HashSet中的contains可以判断哈希表中是否有这个值

那么根据题目，我们可以提炼的关键点：

• 和为 0 且不重复的三元组

题目解答

Java题解一

思路分析

首先我们使用的哈希表法，即先排序，接着使用两个for循环，求出其中两个元素的和，然后剩下的一个一个元素使用哈希表来判断是否有这个值（注意去重）

• 对数组元素排序
• 然后使用双重for循环，同时要去掉重复元组
• 满足条件的加入set

class Solution {    public List<List<Integer>> threeSum(int[] nums) {//处理特殊情况      if(nums.length<3)  return new ArrayList<List<Integer>>();//实例化只需要最外层指定具体实现集合类      List<List<Integer>> res = new ArrayList<List<Integer>>();//初始化结果集合      Arrays.sort(nums); //排序for(int i=0;i<nums.length;i++){     if(i>0 && nums[i]==nums[i-1])  continue; //去掉重复元组     int target = -nums[i];     HashSet<Integer> set = new HashSet<Integer>(); //集合来判断是否满足条件     for(int j=i+1;j<nums.length;) {  //如果存在元素满足条件，执行以下逻辑  if(set.contains(target-nums[j])){      ArrayList<Integer> tmp = new ArrayList<Integer>();      tmp.add(nums[i]);      tmp.add(nums[j]);      tmp.add(target-nums[j]);      res.add(tmp);      //如果寻找到解，那么不需要将nums[j]加入set，因为此时已经将nums[j]作为答案赋值给res了，nums[j]已经不可能和其他元素搭配组成答案了。      //寻找到一个解，如果下一个元素值和当前值一样，那么会出现一个重复的答案，所以直接跳过，直到出现不一样的元素      j++;      while(j<nums.length&&nums[j]==nums[j-1]){   j++;      }  }else{      //如果当前元素不存在，同时也不满足解条件，那么将当前元素加入set      set.add(nums[j++]);  }     } }     return res;    }}

Java题解二

思路分析

第二种方法是双指针法，即首先对数组排序，然后利用双指针的移动来找出满足条件的值。具体思路如下：

• 首先排序，方便去重
• 接着定义第一个固定的指针k，用来实现遍历
• 然后是双指针的左右指针i和j，左指针i在k的后面，右指针j在数组最右边
• 在左右指针不交叉的情况下，左指针右移，右指针左移
• 满足条件加入List集合；不满足的话，移动固定指针后，重复上面步骤

代码实现

class Solution {    public List<List<Integer>> threeSum(int[] nums) {   Arrays.sort(nums); //数组排序，方便去重 List<List<Integer>> res = new ArrayList<>(); //结果集合 for(int k = 0; k < nums.length - 2; k++){ //k是第一个固定的指针     if(nums[k] > 0)  //k位置的都大于0了，后面的肯定都大于0了  break;     if(k > 0 && nums[k] == nums[k - 1])  //去重  continue;     int i = k + 1; //双指针的左边的指针     int j = nums.length - 1;  //双指针的右边的指针     while(i < j){ //满足左边指针在左边，右边指针在右边（不交叉）  int sum = nums[k] + nums[i] + nums[j]; //求和  if(sum < 0){ //和小于0，左边指针向右移动      while(i < j && nums[i] == nums[++i]);  } else if (sum > 0) {//和大于00，右边指针向左移动      while(i < j && nums[j] == nums[--j]);  } else { //和等于0，满足条件，元素放入结果集合      res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));      //想要找下一个0的话，必须左指针元素值增加，右指针元素值减小      while(i < j && nums[i] == nums[++i]);//左指针继续右移（在0的基础上增加）      while(i < j && nums[j] == nums[--j]); //右指针继续左移（在0的基础上减少）  }     } } return res; //返回结果集合    }}