算法day04

第一题 ：

209. 长度最小的子数组

有上题可知，我们会采用双指针和单调性的思路来解决

        我们本题采用左右双指针从数组的0位置同向前进，所以将此类模型称为滑块；

步骤思路如下：

步骤一：

        定义所有双指针都指向数组的0号位置；

步骤二：数组进窗口

        右指针开始向右移动；

步骤三：判断是否数组进窗口或者出窗口

        当当前窗口中的数字sum小于t时，右指针继续向右移动，直到数组之和大于等于t；

        如上图所示，当前的左指针向右移动，将左指针之前所指的元素退出窗口；

此时重复上述的操作，直到right指针到达数组的最右端；

同时我们每一次在判断sum和要要求值之后都要更新len变量的结果

        代码如下所示：

class Solution {public int minSubArrayLen(int target, int[] nums) {int n = nums.length,sum = 0,lenght = Integer.MAX_VALUE;for(int left = 0,right = 0;right < n;right++){sum +=nums[right];while(sum >= target){lenght = Math.min(lenght,(right-left+1));sum -=nums[left];left ++;}}return lenght == Integer.MAX_VALUE ? 0:lenght;}
}

第二题：

3. 无重复字符的最长子串

如上题所示：

        本题采用滑块的相关知识点，如上题故事；

本题主要会采用如下的创新点：

 //把字符串变成字符数组,s1里面的每一个元素都是每一个字符的ascall值

    char[] s = ss.toCharArray();

//用数组模拟哈希表

//即用数组的下标为0的字符来表示ascall值为1 的数组。。。

//用数组里面的数字来表示该字符在hash值里面出现的次数

    int[] hash = new int[128];

用ascall值来映射数组中的字符，同时用数组来类似于hash表，当hash表中存放相应字符的出现次数，每次有相应的字符进入滑块，该字符的出现次数加一，当该hash中相应的位置如果存放的数值大于一时，则滑块中有重复的字符，应该采取进一步的措施；

解题步骤如下：

步骤一：

        定义所有双指针都指向数组的0号位置；

步骤二：数组进窗口

        让字符开始进入hash表；该数组存放的hash表的位置上数据+1；

判断当右指针所指的hash表中数据>1时，我们要移动左指针，将之前进入到窗口里面的元素出去，同时hash表中的数据--；

        同时每一次元素出窗口之后要更新窗口长度并记录在案；

代码如下所示：

class Solution {public int lengthOfLongestSubstring(String ss) {//把字符串变成字符数组,s1里面的每一个元素都是每一个字符的ascall值char[] s = ss.toCharArray();//用数组模拟哈希表//即用数组的下标为0的字符来表示ascall值为1 的数组。。。//用数组里面的数字来表示该字符在hash值里面出现的次数int[] hash = new int[128];int n = s.length;int  res =  0;for(int left = 0,right = 0;right < n;){hash[s[right]] ++;while(hash[s[right]] > 1){hash[s[left]] --;left ++;res= Math.max(res,right-left+1); }res= Math.max(res,right-left+1);right++;} return res;}
}

ps：本次的内容就到这里了，如果对你有所帮助的话，就请一键三连哦，文章图片是我喜欢的xox，在这里给大家安利一下哦！！！