【每日一道算法】 算法·每日一题（详解+多解）-- day6
✨博主介绍
数组中和为 0 的三个数
解题思路
💫点击直接资料领取💫
✨博主介绍
🌊 作者主页：苏州程序大白
🌊 作者简介：🏆CSDN人工智能域优质创作者🥇，苏州市凯捷智能科技有限公司创始之一，目前合作公司富士康、歌尔等几家新能源公司
💬如果文章对你有帮助，欢迎关注、点赞、收藏
💅 有任何问题欢迎私信，看到会及时回复
💅关注苏州程序大白，分享粉丝福利
数组中和为 0 的三个数
给定一个包含 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
解题思路
排序+暴力
时间复杂度O(N3)，空间复杂度O(1)
枚举第一个数，然后再使用双指针。
首先排序，为了避免重复需要保证nums[i] != nums[i-1]，
举例：[-6, -6, 3, 3]。
因为存在多组数据所以还需要在除了第一次确定以外，排除重复的
举例：[-6, 2, 3, 3, 3, 3, 4, ]：可能的结果[-6, 2, 4], [-6, 3, 3], ==[-6, 3, 3]==这个已经重复了，所以需要排除
排除重复while (left
如果没有重复进入下一个索引left++;
时间复杂度O(N2)，空间复杂度O(N)：结果空间。
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); int n=nums.length; for (int i=0; i<n-2; i++){ if (i>0 && nums[i] == nums[i-1]) continue; int left = i+1; int right = n-1; while(left<right){ int cur = nums[i] + nums[left] + nums[right]; if (cur<0) left++; else if (cur>0) right--; else { res.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left<right && nums[left] == nums[left+1]) left++; while (left<right && nums[right] == nums[right-1]) right--; left++; right--; } } } return res; } }
双指针
要把双指针的思路应用到三元组上, 就必须将问题化为双指针类型。
设数组元素 a,b,c, a + b + c = 0;
则 -a = b + c;
先针对一个元素 a, 从数组中找到两个元素 b、c 使之 b + c = -a;
这样一来, 问题就化简为: 找到数组中两个元素和为 -a。
题目变成了两个元素XXX, 那么我们就好使用双指针来解决这道问题了。
我们先对数组进行排序, 来保证双指针的有序查找。
Arrays.sort(nums);
我们枚举每一个不重复的 a, 来保证已经出现的 (b + c) 组合不再重复。
为了达到这个效果, 我们可以先确定一个旧值 lastNum, 将当前值与旧值比较; 如果不相同, 则开始搜索满足条件的三元组。
class Solution { public List<List<Integer>> threeSum(int[] nums) { if (null == nums || 3 > nums.length) { return new ArrayList<>(); } Arrays.sort(nums); int lastNum = Integer.MAX_VALUE; List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < nums.length - 1; i++) { if (nums[i] == lastNum) { continue; } lastNum = nums[i]; int left = i + 1; int right = nums.length - 1; int target = -nums[i]; int sum; while (left < right) { sum = nums[left] + nums[right]; if (sum == target) { result.add(Arrays.asList(lastNum, nums[left], nums[right])); ++left; while(left < right && nums[left] == nums[left-1]){ ++left; } --right; while (left < right && nums[right] == nums[right + 1]) { --right; } } else if (sum > target) { --right; } else { ++left; } } } return result; } }
三数之和，可以将其看成两数之和，再与第三个数之和对于两数之和，采用二分查找的思路
二分查找的一个非常重要的前提条件是数组是有序的，所以在查找之前先对数据进行排序遍历当前数组，目标值变为0-nums[i]二分查找和为0-nums[i]的两个数二分查找代码块。
vector<vector<int>> process(vector<int>&nums,int target,int i,int n){ int left=i,right=n; vector<vector<int>> res; while(left<right){ int temp=nums[left]+nums[right]; int lval=nums[left],rval=nums[right];//记录当前左右指针指向的值，因为遇到重复的值这样可以直接跳过 if(temp<target){ while(left<right&&nums[left]==lval)left++; } if(temp>target){ while(left<right&&nums[right]==rval)right--; } if(temp==target){ res.push_back({nums[left],nums[right]}); while(left<right&&nums[left]==lval)left++; while(left<right&&nums[right]==rval)right--;//找到目标值了，left和right也要改变，这里记录一下，因为自己经常忘 } } return res; }
主函数模块
vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end());//先对数组进行排序 int n=nums.size()-1; vector<vector<int>> res; for(int i=0;i<n-1;++i){ vector<vector<int>> temp=process(nums,0-nums[i],i+1,n);//寻找的范围是当前值后面的那个值一直到最后 if(!temp.empty()){ for(auto x:temp){ x.push_back(nums[i]); res.push_back(x); } } while(i<n-1&&nums[i+1]==nums[i])i++;//这里同样用来排除重复值 } return res; }
