力扣每日一练之数组上篇Day1

🍕前面的话🥞

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

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

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

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

😘系列专栏：java学习

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

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

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

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

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

🏓导航小助手📻

🏈Leetcode 217.存在重复元素👓

👛题目详情👒

217. 存在重复元素

难度简单

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false

 > 示例 1：
 >
 > 输入：nums = [1,2,3,1]
 >        输出：true
 > 示例 2：
 >
 > 输入：nums = [1,2,3,4]
 >        输出：false
 > 示例 3：
 >
 > 输入：nums = [1,1,1,3,3,4,3,2,4,2]
 >        输出：true
 ​
 ​

🥏解题思路

首先，分析题目，确定用什么方法，这道题我们可以使用数组排序，即为把数组排序之后，判断相邻元素是否相等，假如相邻元素相等，则在数组中出现至少两次。分析完之后，我们就可以开始写代码了。

首先我们需要定义一个数组，变量为nums。之后呢，我们用for循环，遍历每一个数。最后，用if语句来判断相邻的两个数是否相等，返回真或者假。

🎇注意点

1.首先呢，我们的数组里，有多个数，所以应该用nums

2.for循环中，应该是使用num的长度作为第二个判断

3.++i与i++没有实质上的区别，都可以使用，只不过参加竞赛的同学可能习惯使用++i

4.=为单纯的变量赋值，==为比较值是否相同

🍪源代码

 class Solution {
     public boolean containsDuplicate(int[] nums) {
         Arrays.sort(nums);
         for (int i = 0; i < nums.length - 1; ++i) {
             if (nums[i] == nums[i + 1]) {
                 return true;
             }
         }
         return false;
     }
 }
 ​
 ​

🪐LeetCode53 最大子数组和

🛬题目描述🚉

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

     示例 1：
 ​
 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
        输出：6
        解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 ​
 •       示例 2：
 ​
 输入：nums = [1]
        输出：1
 ​
 •       示例 3：
 ​
 输入：nums = [5,4,-1,7,8]
        输出：23
 ​
 ​

🚧解题思路

首先，这个题目有一个比较简单的解法，就是通过两层for循环找出所有的连续子数组，通过对比得到最大的和。然后，每一次都计算一下，这样的话可以得到所有的连续子数组，复杂度是O（n*n）

然后，今天介绍的方法是动态规划，可以把时间复杂度降低为O（n），也就是遍历一次就可以做出来，之后我们以第一个示例来看，从1开始遍历，相加的和和下一个数进行比较。

最后，开始写代码，需要一个变量maxSumEndAtHere，设置为数组的第一位，之后用for循环遍历，从数组的第二位开始，之后用Math的最大值比较公式进行比较，比较两个值，找出更大的一个，之后，我们需要输出全局的最大值，顺便每次比较出全局的最大值，最后一步，输出全局的最大值，这就是这道题的解法

⚓源代码

 class Solution {
     public int maxSubArray(int[] nums) {
         int maxSumEndAtHere=nums[0];
         int max=nums[0];
         for(int i=1;i<nums.length;i++){
             maxSumEndAtHere=Math.max(nums[i],maxSumEndAtHere+nums[i]);
             max=Math.max(maxSumEndAtHere,max);
         }
         return max;
     }
 }

🌌总结

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

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