力扣每日一练之数组中篇 Day2

🍕前面的话🥞

大家好！本篇文章将介绍 2 周搞定数据结构的题，来自力扣的 1.两数之和和 88.合并两个有序数组，本文将以这两道题作为背景，介绍经典的数组排序以及线性查找，展示语言为 java（博主学习语言为 java)。今天呢，是博主开始刷力扣的第二天，如果有想要开始准备自己的算法面试的同学，可以跟着我的脚步一起，共同进步。大家都是并肩作战的伙伴，一起努力奋力前行，路漫漫其修远兮，吾将上下而求索，相信我们一定都可以拿到自己期望的 offer，冲冲冲！

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn 首发！

😘系列专栏：java 学习

💻首发时间：🎞2022 年 4 月 30 日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🔏参考在线编程网站：🎧力扣

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

🏓导航小助手📻

[TOC]

💥LeetCode1 两数之和💝

💤题目详情💦

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
输入：nums = [3,2,4], target = 6输出：[1,2]示例 3：
输入：nums = [3,3], target = 6输出：[0,1]
。

💫解题思路

🥌题目讲解

这道题有很多种方法，因为博主本人呢，算法还没有学多少，所以我们在这里只提供第一种解法，也是更好理解的一种办法，好的，下面我们来具体看看如何解决叭

首先，这道题给我们的是一个数组 nums 以及一个和 target，找到两个元素之和为 target，再返回两个数之和就可以了，这样的话，我们可以发现，可能最后有多个解，但是这个题目也说明了，只要返回一个解，就算运行成功了。但是要注意，同一个元素，不能使用两次。

🎑暴力解法【线性查找】

一开始我们会采用最暴力的解法，也就是线性查找。首先，我们从第一个元素开始，固定第一个元素，之后我们用 target 减掉第一个数得到的，去查找有没有这个值。查找方式为用指针向后一个一个查找，这就是线性查找、如果没有找到的话，我们就固定第二个元素。之后以此类推寻找第二个元素有没有对应的值，没有找到的话，我们接着寻找第三个值，如果找到了，那我们就返回对应的 i，j 值，也就是它们的角标。

之后我们就开始写代码了，第一步，先输入数组和 target，也就是定义这两个值。第二步，我们用 if 语句进行一个特判，就是判断数组是否为空，以及数组的长度是否为 0，在这两种情况下，都无法选出两个值。之后第三步，由于我们使用的是暴力查找，所以先定义一个 for 循环，然后我们先固定一个元素的值，定义为 x。之后第四步，我们定义一个变量为 i+1，当满足题中的条件时，即可返回数组的角标。

接下来我们来分析一下时间复杂度和空间复杂度，因为我们没有开辟任何新的数组空间，所以空间复杂度为 O（1）

当 i=0 时，需要比较 n-1 次，数组的长度为 n。当 i=1 时，需要比较 n-2 次。一直到比较 1 次，所以比较的次数是(n-1)+(n-2)+…+1,这个是第二个 for 语句要执行的次数，经过数学计算以及化简，最终得到时间复杂度为 O（n*n）

🩳注意点

1.首先设置一个前提条件就是数组不为空，用 null 表示，以及长度不为 0

2.i 是从 0 开始的，到最后一个结束，所以不应该减掉 1

3.j 是从 i 之后遍历的

💨源代码

class Solution {    public int[] twoSum(int[] nums, int target) {        if(nums==null||nums.length==0)        return new int[0];        for(int i=0;i<nums.length;i++){            int x=nums[i];            for(int j=i+1;j<nums.length;j++){                if(nums[j]==target-x){                    return new int[]{i,j};                }            }        }        return new int[0];    }   }

🎄LeetCode 88.合并两个有序数组

🎉题目详情🎊

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3输出：[1,2,2,3,5,6]解释：需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0输出：[1]解释：需要合并 [1] 和 [] 。合并结果是 [1] 。示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1输出：[1]解释：需要合并的数组是 [] 和 [1] 。合并结果是 [1] 。注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

👡解题思路

直接合并后排序

思路：最直观的方法就是先将数组 num2 放进 nums1 的尾部，然后直接对整个数组进行排序

首先题目已经给我们提示定义好了两个数组以及两个变量 m，n，之后用一个 for 循环，定义 i 并且设置条件为 i 不等于 n，意思就是把第二个数组的内容放到第一个数组的后面，然后用一个排序得出 nums1

class Solution {    public void merge(int[] nums1, int m, int[] nums2, int n) {        for (int i = 0; i != n; ++i) {            nums1[m + i] = nums2[i];        }        Arrays.sort(nums1);    }}

复杂度分析

时间复杂度：O((m+n)\log(m+n))O((m+n)log(m+n))。排序序列长度为 m+nm+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)\log(m+n))O((m+n)log(m+n))

空间复杂度：O(\log(m+n))O(log(m+n))。排序序列长度为 m+nm+n，套用快速排序的空间复杂度即可，平均情况为 O(\log(m+n))O(log(m+n))

🌌总结

通过这两道题，我们学会了线性排列和排序算法，复习了数组和循环的知识，那么呢，期待一下下一篇文章吧，和我一起进步，每天努力多一些，迈出更大的一步

觉得文章写的不错的亲亲，点赞评论关注走一波，爱你们哦🛴