卷进大厂系列之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; //返回结果集合 }}