【迎战蓝桥杯】算法·每日一题（详解+多解）-- day6

苏州程序大白

发布于 2022-05-07 00:37:30

17800

代码可运行

文章被收录于专栏：用户8907256的专栏用户8907256的专栏

运行总次数：0

代码可运行

【每日一道算法】算法·每日一题（详解+多解）-- day6

✨博主介绍

🌊 作者主页：苏州程序大白 🌊 作者简介：🏆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<right && nums[left] == nums[left+1]) 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;
}