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

2年前 (2022) 程序员胖胖胖虎阿

115 0 0

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

🍕前面的话🥞

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

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

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

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

😘系列专栏：java学习

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

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

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

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

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲
💬推荐一款模拟面试、刷题神器👉点击进入网站

🏓导航小助手📻

文章目录

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

@[toc]

🏈Leetcode 217.存在重复元素👓

👛题目详情👒

[217. 存在重复元素](https://leetcode-cn.com/problems/contains-duplicate/)

🥏解题思路

🎇注意点

🍪源代码

🪐LeetCode53 最大子数组和

🛬题目描述🚉

🚧解题思路

⚓源代码

🌌总结

🌌总结

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

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

🏈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;
    }
}