每日算法题（十四）俩数组题+详解

野性酷女 2023-09-23 17:01 69阅读 0赞

“凡事预则立，不预则废”

**------持续更新入门系列算法实例--------**

**如果你也喜欢Java和算法，欢迎订阅专栏共同学习交流！**

**你的点赞、关注、评论、是我创作的动力！**

**-------希望我的文章对你有所帮助--------**

> **前言：** **算法的4学习需要一定时间来积累做题技巧以及构建各种数据类型的解题思维和模型，因此需要持续的刷题去扩展自己的知识库，总结不同类型题目的特点和模板。**
> 
>  **既然决定了参加明年4月份的Blue杯，就要全力以赴。希望那一天我能够胸有成竹、泰然自如去应对竞赛！并且有所成就，愿你见证我的成长！**

**目录**

一、有序数组的平方

题目描述

二、代码实现

一、长度最小的子数组

题目描述

二、代码实现

--------------------

## 一、有序数组的平方 ##

### 题目描述 ###

给你一个按 **非递减顺序** 排序的整数数组 `nums`，返回 **每个数字的平方** 组成的新数组，要求也按 **非递减顺序** 排序。

**示例 1：**

>     输入：nums = [-4,-1,0,3,10]
>     输出：[0,1,9,16,100]
>     解释：平方后，数组变为 [16,1,0,9,100]
>     排序后，数组变为 [0,1,9,16,100]

**示例 2：**

>     输入：nums = [-7,-3,2,3,11]
>     输出：[4,9,9,49,121]

> **解题思路：**1、常规方法比较简单，即将数组中的数平方后存在一个新数组，再进行升序排序。
> 
> 2、本次使用双指针进行解题。
> 
> 3、因为考虑到负数的平方可能会大于最后一个数，因此在存入双指针时要进行比较大小。
> 
> 4、设定left、right指针分别在数组首位和末位，因为末位数必然是最大的，因此比较Array\[left\]和Array\[right\]两个数的平方。
> 
> 5、哪个大就存到新数组的最后一个位置去，并且移动对应的指针，最后即可得到升序后的新数组。
> 
> 6、动图演示：
> 
> ## ![cbff8976cdf04e3e80ff80aab9b76b64.gif][] ##

## 二、代码实现 ##

class Solution {
        public int[] sortedSquares(int[] nums) {
            int letf=0,right=nums.length-1;
            int Result[]=new int[nums.length];
            int k=nums.length-1;
            while(letf<=right){
                if(nums[letf]*nums[letf]>nums[right]*nums[right]){
                Result[k--]=nums[letf]*nums[letf];
                ++letf;
                }
                else{
                    Result[k--]=nums[right]*nums[right];
                    --right;
                }
               
            }
              return Result;
        }
       
    }

## 一、长度最小的子数组 ##

### 题目描述 ###

给定一个含有 `n`个正整数的数组和一个正整数 `target` **。**

找出该数组中满足其和`≥ target`的长度最小的 **连续子数组** `[numsl, numsl+1, ..., numsr-1, numsr]` ，并返回其长度**。**如果不存在符合条件的子数组，返回 `0` 。

**示例 1：**

>     输入：target = 7, nums = [2,3,1,2,4,3]
>     输出：2
>     解释：子数组[4,3]是该条件下的长度最小的子数组。

**示例 2：**

>     输入：target = 4, nums = [1,4,4]
>     输出：1

**示例 3：**

>     输入：target = 11, nums = [1,1,1,1,1,1,1,1]
>     输出：0

> **解题思路：**1、本题有点类似于之前的最长字符前缀问题，需要不断更新符合条件的长度
> 
> 2、本题通过滑动窗口来实现，即符合条件的窗口长度会不断改变，且初始值都是为下一个元素。
> 
> 3、通过Sum累加获取符合条件的窗口长度，遍历完数组后返回最短的窗口长度即可。
> 
> 4、动图演示：
> 
> 5、tips：注意要将初始窗口长度赋值为比原数组长度更大的值，才能最后进行判断！
> 
> ![3c039e25733e4a308a1539cfce9bb445.gif][]

## 二、代码实现 ##

class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int Length=0, Slength=nums.length+1;//窗口长度、最短子数组长度初始化
            int Sum=0,k=0;
            for(int i=0;i<nums.length;i++){
                Sum+=nums[i];
                while(Sum>=target){
                    Length=i-k+1;//获取当前窗口长度
                    Slength=Math.min(Length,Slength);//如果更小则更新值
                    Sum-=nums[k++];//实现窗口的后移
    
                }
            }
            return Slength==nums.length+1?0:Slength;//如果最短子数组长度没有改变说明没有和为target
        }
    }

**感谢爱学习的你学到了最后，点个赞、关注支持一下吧！**

[cbff8976cdf04e3e80ff80aab9b76b64.gif]: https://img-blog.csdnimg.cn/cbff8976cdf04e3e80ff80aab9b76b64.gif
[3c039e25733e4a308a1539cfce9bb445.gif]: https://img-blog.csdnimg.cn/3c039e25733e4a308a1539cfce9bb445.gif