【每日一道算法】 算法·每日一题（详解+多解）-- 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(N³)，空间复杂度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<right && nums[left] == nums[left+1]) left++;
  • 如果没有重复进入下一个索引left++;

• 时间复杂度O(N²)，空间复杂度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;}

💫点击直接资料领取💫

❤️关注苏州程序大白公众号❤️

👇 👇👇