算法-数组
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法-数组，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含19224字，纯文字阅读大概需要28分钟。
内容图文
目录
在做数组相关的问题的时候考虑双指针，指针对撞及滑动窗口
-
二分查找法
必须是有序的数组，返回查找到的索引
/**
*二分查找法，查找的数组必须是有序的.在[l...r]范围内进行二分查找
*/
public static int binarySearch(int[] arr,int n,int target){
//在[l...r]闭区间中进行查找
int l = 0;
int r = n-1;
while (l<=r){
int mid = l+(r-l)/2;
if(arr[mid]==target){
return mid;
}else if(arr[mid]>target){
r=mid-1;
}else{
l=mid+1;
}
}
return -1;
}
leetcode283-移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
思路：将不是零的元素依次往前移动，两个索引，i遍历数组，j表示有几个不是0的元素。将非0元素往前移动之后把该位置置零
public static void moveZeroes(int[] nums){
//代表非0元素的数量
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=0){
nums[j]=nums[i];
//若i和j不是同一个位置，要将i位置置零
if(i!=j){
nums[i]=0;
}
j++;
}
}
}
leetcode75-颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
思路：统计出三个颜色的个数，再重写数组
public void sortColors(int[] nums) {
if(nums.length==0){
return;
}
int r = 0;
int w = 0;
for(int i=0;i<nums.length;i++){
if(nums[i]==0){
r++;
}
if(nums[i]==1){
w++;
}
}
for(int j=0;j<r;j++){
nums[j]=0;
}
for(int j=r;j<r+w;j++){
nums[j]=1;
}
for(int j=r+w;j<nums.length;j++){
nums[j]=2;
}
}
leetcode167-两数之和2-输入有序数组-对撞指针
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
思路：对撞指针，从最左边和最右边开始索引，若和大于目标数，将右边的指针左移，若和小于目标数将左边的指针右移。重点：升序排列。注意：返回值的索引从1开始。
public int[] twoSum(int[] numbers, int target){
if(numbers.length==0){
return null;
}
int l=0;
int r = numbers.length-1;
while (l<r){
if(numbers[l]+numbers[r]==target){
break;
}else if(numbers[l]+numbers[r]>target){
r--;
}else{
l++;
}
}
int[] res = {l+1,r+1};
return res;
}
leetcode209-长度最小的子数组-滑动窗口
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
思路：从第一个数开始如果和比s小的话就扩大窗口，达到大于s后记录此时的子数组长度，窗口前面去掉一个数再判断是否大于s，不大于的话扩大窗口，直到大于s，将再次获得的子数组长度与之前的比较，保留最小的，知道滑动到数组最后。需要两个索引，分别指向滑动窗口的开始位置和结束位置。
public static int minSubArrayLen(int s, int[] nums){
if(nums.length==0){
return 0;
}
//在[i...j]区间内进行滑动
int i=0;
int j=-1;
int sum = 0;
int res = nums.length+1;
while (i<nums.length){
if(j+1<nums.length&&sum<s){
sum += nums[++j];
}else{
sum -= nums[i++];
}
if(sum>=s){
res = min(res,j-i+1);
}
}
if(res==nums.length+1){
return 0;
}
return res;
}
leetcode3-无重复字符的最长字串-滑动窗口
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：一共有256个字符，使用一个freq[256]数组来统计各个字符出现的次数。使用滑动窗口来寻找最长子串。
public int lengthOfLongestSubstring(String s) {
//滑动窗口，比较是否重复使用freq[256]对应位置比较
int l = 0;
int r = -1;
int res = 0;
int[] freq = new int[256];
while (l < s.length()) {
if (r + 1 < s.length() && freq[Integer.valueOf(s.charAt(r + 1))] == 0) {
freq[Integer.valueOf(s.charAt(++r))]++;
} else {
freq[Integer.valueOf(s.charAt(l))]--;
l++;
}
res = max(res, r - l + 1);
}
return res;
}
习题
leetcode27-移除元素
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
思路：遍历数组，创建变量j代表非目标的元素，若遍历的非目标元素则将非目标元素放到j的位置，j++
public int removeElement(int[] nums, int val) {
if(nums.length==0){
return 0;
}
//j代表非目标元素的个数
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
nums[j]=nums[i];
j++;
}
}
return j;
}
leetcode26-删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
思路：遍历数组，当其值不等于前面的值的时候移动到j索引的位置，j++，j代表不重复的元素的个数
public int removeDuplicates(int[] nums) {
if(nums.length==0){
return 0;
}
//记录不重复的值的个数
int j=0;
for(int i=0;i<nums.length;i++){
if(i==0){
nums[j]=nums[i];
j++;
}else if(nums[i]!=nums[i-1]){
nums[j]=nums[i];
j++;
}
}
return j;
}
leetcode80-删除排序数组中的重复项2
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,1,2,3,3],
函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
你不需要考虑数组中超出新长度后面的元素。
思路：判断其前面两个数是否相同，如果只有一个相同则加入数组，如果有两个则不加入数组，j仍旧为最后数组的元素数量。
public int removeDuplicates(int[] nums) {
if(nums.length==0){
return 0;
}
//j代表新数组的长度
int j=0;
for(int i=0;i<nums.length;i++){
if(i==0||i==1){
nums[j]=nums[i];
j++;
}else if(nums[i]!=nums[j-1]){
nums[j]=nums[i];
j++;
}else if(nums[i]==nums[j-1]&&nums[i]!=nums[j-2]){
nums[j]=nums[i];
j++;
}
}
return j;
}
leetcode88-合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
思路：copy一个nums1，将copy的数组和nums2数组依次将最小的数往nums1里面放（归并排序的思想）
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int[] aux = new int[m];
for(int i=0;i<m;i++){
aux[i]=nums1[i];
}
//遍历aux数组
int i=0;
//遍历nums2数组
int j=0;
//最终结果nums1
int k;
for(k=0;k<m+n;k++){
if(i>=m){
nums1[k]=nums2[j];
j++;
}else if(j>=n){
nums1[k]=aux[i];
i++;
}else if(aux[i]<nums2[j]){
nums1[k]=aux[i];
i++;
}else{
nums1[k]=nums2[j];
j++;
}
}
}
leetcode125-验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
思路：从两端开始索引，索引同时执行++和--操作找到第一个字母然后比较字母时候相同，当比较到左右索引相遇时说明是回文字符串。思考：怎么判断是否为字符和数字，和大小写问题。解决：将字符串转换为只有字母和数字的字符串并将字符串全部转换为小写。
public static boolean isPalindrome(String s) {
if(s.length()==0){
return true;
}
s = s.toLowerCase();
int l = s.length();
//用来接收去掉除字母和数字以后的新字符串
StringBuilder str = new StringBuilder();
for(int i=0;i<l;i++){
if((s.charAt(i)>='0'&&s.charAt(i)<='9')||(s.charAt(i)>='a'&&s.charAt(i)<='z')){
str.append(s.charAt(i));
}
}
int i =0;
int j=str.length()-1;
//从两头开始遍历字符串
while (true){
if(i>=j){
return true;
}
if(str.charAt(i)==str.charAt(j)){
i++;
j--;
}else{
return false;
}
}
}
leetcode344-反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路：将第一个和最后一个对调，将第二个和倒数第二个对调，依次类推，如果未为技术个，中间一个不用交换，交换也行。
public void reverseString(char[] s) {
int i = 0;
int j = s.length - 1;
while (true) {
if (i >= j) {
break;
}
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
leetcode345-反转字符串中的元音字母
编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
输入: "hello"
输出: "holle"
示例 2:
输入: "leetcode"
输出: "leotcede"
说明:
元音字母不包含字母"y"。
思路：原因字母为aeiou，从左到右找到的第一个元音字母与从右到左找到的第一个元音字母交换，再依次交换第二个第三个。思考：怎么判断是否为元音字母：将所有元音字母存储在一个数组中，每索引到一个字符判断它是否在数组中。注意！！!题目中没有说大小写。可以将判断一个字符是否是元音字母的方法独立出来写一个函数。
public static String reverseVowels(String s) {
char[] str = s.toCharArray();
int i = 0;
int j = str.length - 1;
while (true) {
if (i >= j) {
return new String(str);
}else if (isVowels(str[i]) && isVowels(str[j])) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
i++;
j--;
}else if(isVowels(str[i])){
j--;
}else{
i++;
}
}
}
/**
* 判断字符是否为元音
*/
private static boolean isVowels(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U';
}
leetcode11-盛最多水的容器
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且n的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例:
输入: [1,8,6,2,5,4,8,3,7] 输出: 49
思路：暴力解法：i和j分别为左边界和右边界，移动右边界获取获取水的容量。遍历到数组右边，再将左边界i向右移，移动后的i作为左边界，再将j定位在i的后面一个位置，再次遍历。直到将所有的可能结果计算一边，每次都要判断一哪个值比较大，保留最大的值。思考：有没有时间复杂度小于O(n^2）的，不用扫描两次数组。
暴力解法：
public int maxArea(int[] height) {
//初始化结果为-1
int res = -1;
//左边界的所有可能结果
for(int i=0;i<height.length-1;i++){
for(int j=i+1;j<height.length;j++){
int temp = min(height[i],height[j])*(j-i);
res = max(temp,res);
}
}
return res;
}
优化解法：双指针，首先将指针放在两侧，移动指针时考虑，移动指针必然使得宽度变小，但如果移动比较低的那一根指针可能使面积变大。所以每次都移动比较低的那一根指针，才有可能获得比之前面积更大的值，来获取最大的面积。
public int maxArea(int[] height){
//开始的时候让指针位于两端
int i=0;
int j=height.length-1;
int maxarea = -1;
while (i<j){
maxarea = max(maxarea,min(height[i],height[j])*(j-i));
if(height[i]<height[j]){
i++;
}else{
j--;
}
}
return maxarea;
}
leetcode438-找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
示例 2:
输入:
s: "abab" p: "ab"
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
思路：粗暴解法：遍历一边字符串s，对每一个字符，判断其自身和后面两位字符是否和p字符串相同。不能通过leetcode，时间复杂度太高，超出时间限制。
public static List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if(p.length()>s.length()||s.length()==0||p.length()==0){
return res;
}
for(int i = 0;i<s.length()-p.length()+1;i++){
if(isEqual(s,i,p)){
res.add(i);
}
}
return res;
}
/**
*判断字符串s的索引位l处的字符开始，其后是否存在与p相同的异位词
*/
private static boolean isEqual(String s,int l,String p){
char[] str = new char[p.length()];
for(int i=0;i<p.length();i++){
str[i] = s.charAt(l+i);
}
Arrays.sort(str);
char[] pstr = p.toCharArray();
Arrays.sort(pstr);
for(int i=0;i<str.length;i++){
if(str[i]!=pstr[i]){
return false;
}
}
return true;
}
优化：维护两个数组freqs[26]和freqp[26]分别代表两个字符串中就那些字符，存在这个字符该位置为1，不存在这个字符该位置默认为0，先计算freq[26]且保持不变。使用窗口大小为p的窗口在s上滑动，在滑动过程中freqs[26]记录窗口中有哪些值，每次滑动的时候用Array.equals(freqs[26],freqp[26])来比较两个数组是否相等，相等说明是一个异位字串，将索引加入结果中。
public static List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (p.length() > s.length() || s.length() == 0 || p.length() == 0) {
return res;
}
//用来记录滑动窗口和p串中的字符
int[] freqs = new int[26];
int[] freqp = new int[26];
int l=0;
int r=-1;
for (int i = 0; i < p.length(); i++) {
freqp[p.charAt(i) - 'a']++;
freqs[s.charAt(++r)-'a']++;
}
if(Arrays.equals(freqs,freqp)){
res.add(l);
}
while (l<s.length()-p.length()){
freqs[s.charAt(l++)-'a']--;
freqs[s.charAt(++r)-'a']++;
if(Arrays.equals(freqs,freqp)){
res.add(l);
}
}
return res;
}
leetcode-最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：
如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
思路：好难啊！滑动窗口，首先将T中包含的所有字母及其数量存储在一个map中，然后使用滑动窗口遍历，滑动过程中，将字符及其数量存储在另一个map中。第一个map存储了n个字符及其个数，在窗口滑动过程中，当有字符满足条件时，计数器加1，直到n个条件全部满足，说明找到了第一个符合条件的字串。将结果存入一个int[length,left,right]数组中，三个参数分别为字串长度，开始索引和结束索引。那么接下来，就可以进行窗口滑动了，先将左边的往前前进一步，将那个字符串在map中出现的值减1，看看这个字符串是否符合要求，不符合要求的话就将计数器减1，满足字串的条件就少一个，于是将右边界向右移动，直到将之前缺失的条件满足，再和之前的结果比较，保留长度最小的字串。大概思路就这样吧，真的好难啊，哭。
public String minWindow(String s, String t) {
if (t.length() > s.length() || s.length() == 0 || t.length() == 0) {
return "";
}
//tMap存储t中的字母及其出现的次数
Map<Character, Integer> tMap = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
if (tMap.get(t.charAt(i)) == null) {
tMap.put(t.charAt(i), 1);
} else {
tMap.put(t.charAt(i), tMap.get(t.charAt(i)) + 1);
}
}
//s中存在t的字串需要满足的条件个数
int required = tMap.size();
//遍历到当前位置，s字串已经满足的条件个数
int format = 0;
int l = 0;
int r = 0;
//用来存放最终结果，数组中的三个数分别为符合条件的字符串的length，left和right
int[] res = {-1, 0, 0};
//用来记录滑动窗口中的字符及其数量
Map<Character, Integer> sMap = new HashMap<>();
while (r < s.length()) {
char c = s.charAt(r);
if (sMap.get(c) == null) {
sMap.put(c, 1);
} else {
sMap.put(c, sMap.get(c) + 1);
}
//判断当前的字符及其个数是否满足字串的其中一个条件，若满足则条件计数器加1
if (tMap.get(c) != null && tMap.get(c).intValue() == sMap.get(c).intValue()) {
format++;
}
while (l <= r && format == required) {
c = s.charAt(l);
//说明当前子串符合条件，将结果与以前的结果对比，保留长度较小的结果
if (res[0]==-1||(res[0]>r-l+1)){
res[0] = r-l+1;
res[1]=l;
res[2]=r;
}
//然后将l右移，map中减掉这个字符，剪掉后弱不不符合条件，将format--；
sMap.put(c,sMap.get(c)-1);
if(tMap.get(c)!=null&&tMap.get(c).intValue()>sMap.get(c).intValue()){
format--;
}
//l要加到不满足条件的时候
l++;
}
//此时不满足条件了，要将r后移
r++;
}
return res[0]==-1?"":s.substring(res[1],res[2]+1);
}
解法2：优化滑动窗口，在S字符串中去掉T中不存在的元素，保留一个S字符串中在T中出现过的字符及其在S字符串的索引。
S = "ABCDDDDDDEEAFFBC" T = "ABC" filtered_S = [(0, 'A'), (1, 'B'), (2, 'C'), (11, 'A'), (14, 'B'), (15, 'C')]
像这个样子，只需要遍历这个列表，就能按照上面的逻辑进行处理。
问题：import javafx.util.Pair;这个包leetcode不让用啊，咋整哦。数组也不行呀，一开始就要确定长度的。优化思想先了解一下。
import javafx.util.Pair;
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
Map<Character, Integer> dictT = new HashMap<Character, Integer>();
for (int i = 0; i < t.length(); i++) {
int count = dictT.getOrDefault(t.charAt(i), 0);
dictT.put(t.charAt(i), count + 1);
}
int required = dictT.size();
// Filter all the characters from s into a new list along with their index.
// The filtering criteria is that the character should be present in t.
List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (dictT.containsKey(c)) {
filteredS.add(new Pair<Integer, Character>(i, c));
}
}
int l = 0, r = 0, formed = 0;
Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();
int[] ans = {-1, 0, 0};
// Look for the characters only in the filtered list instead of entire s.
// This helps to reduce our search.
// Hence, we follow the sliding window approach on as small list.
while (r < filteredS.size()) {
char c = filteredS.get(r).getValue();
int count = windowCounts.getOrDefault(c, 0);
windowCounts.put(c, count + 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
formed++;
}
// Try and co***act the window till the point where it ceases to be 'desirable'.
while (l <= r && formed == required) {
c = filteredS.get(l).getValue();
// Save the smallest window until now.
int end = filteredS.get(r).getKey();
int start = filteredS.get(l).getKey();
if (ans[0] == -1 || end - start + 1 < ans[0]) {
ans[0] = end - start + 1;
ans[1] = start;
ans[2] = end;
}
windowCounts.put(c, windowCounts.get(c) - 1);
if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}
内容总结
以上是互联网集市为您收集整理的算法-数组全部内容，希望文章能够帮你解决算法-数组所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。