209. 长度最小的子数组

#同向双指针 #滑动窗口

209. 长度最小的子数组 - 力扣（LeetCode）

java
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = n + 1; // 用于比较min值，所以需要是n+1
        int s = 0; // 用于计算从left到right的数组和
        int l = 0; // 左指针
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            s += x;
            // 如果num[r]是大于target的，将左指针右移缩小范围
            while (s >= target) {
                // 更新答案
                ans = Math.min(ans, r - l + 1);// r-l+1 计算的是子数组的长度，需要加1
                s -= nums[l]; // 减去左边的值
                l++; // 移动指针
            }
        }
        // 如果循环结束后ans还是等于n+1则相当于没有答案返回0
        if (ans == n + 1) {
            return 0;
        } else {
            return ans;
        }
    }
}

复杂度分析

• 时间复杂度：$O(n)$，对于本题，虽然有两层循环，但是 $l$ 至多可以加 $n$ 次，而不是一般双层循环的可以加 $n^2$ 次，所以是 $O(n)$
• 空间复杂度：$O(1)$，没有使用额外变量数组之类的，故为 $O(1)$

713. 乘积小于 K 的子数组

#同向双指针 #滑动窗口

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

java
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 判断k是否小于1
        if (k <= 1) {
            return 0;
        }
        int n = nums.length;
        int ans = 0;
        float prod = 1; // 用于计算从left到right的数组和
        int l = 0; // 左指针
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            prod *= x;
            // 如果num[r]是大于target的，将左指针右移缩小范围
            while (prod >= k) {
                // 更新答案
                prod /= nums[l]; // 减去左边的值
                l++; // 移动指针
            }
            ans += r - l + 1;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度：$O(1)$

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

#同向双指针 #滑动窗口

3. 无重复字符的最长子串 - 力扣（LeetCode）

java
import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int n = s.length();
        Map<String, Integer> cnt = new HashMap<>();
        int l = 0;
        for (int r = 0; r < n; r++) {
            String rKey = String.valueOf(s.charAt(r));
            cnt.put(rKey, cnt.getOrDefault(rKey, 0) + 1); // 遍历过一个字符，则在哈希表中记录下来
            // ==2说明遇到相同的字符了
            while (cnt.get(rKey) == 2) {
                String lKey = String.valueOf(s.charAt(l));
                cnt.put(lKey, cnt.getOrDefault(lKey, 0) - 1); // 让其左端点减1
                l++;
            }
            ans = Math.max(ans, r - l + 1); // 统计碰到的最大子串长度
        }
        return ans;
    }
}

使用 Java 包装类 HashMap 实现性能不是最优，可考虑 ASCII 字符只有128个，构建一个128字符数组记录字符出现字符即可

java
import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int n = s.length();
        int[] lastIndex = new int[128]; // 存储ASCII字符(128)个，数组的每个值表示字符出现次数
        Arrays.fill(lastIndex, -1); // 初始化数组的每个值都为-1
        int l = 0;
        for (int r = 0; r < n; r++) {
            char c = s.charAt(r);
            l = Math.max(l, lastIndex[c] + 1); // 移动到该字符出现次数的下一个位置
            ans = Math.max(ans, r - l + 1); // 这样就得到了一段无重复字符的字符串 r-l+1是字符串的长度
            lastIndex[c] = r; // 记录字符位置
        }
        return ans;
    }
}

这样耗时和内存占用就更小了

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$，字符总共只能出现128个，所以并不是 n，而 cnt 就不会是 n 的复杂度

2958. 最多 K 个重复元素的最长子数组

#同向双指针 #滑动窗口

2958. 最多 K 个重复元素的最长子数组 - 力扣（LeetCode）

java
import java.util.*;

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        int l = 0;
        // 创建一个数组，记录数字的出现次数
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int r = 0; r < n; r++) {
            int x = nums[r];
            // 遍历数字一次，将其加1
            cnt.merge(x, 1, Integer::sum);
            while (cnt.get(x) > k) {
                int y = nums[l];
                cnt.merge(y, -1, Integer::sum);
                l++;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)$，同向双指针的共同点
• 空间复杂度：$O(n)$，使用了一个 HashMap 存储数字出现次数

2730. 找到最长的半重复子字符串

#相向双指针 #滑动窗口

2730. 找到最长的半重复子字符串 - 力扣（LeetCode）

java
class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        // 转换为字符数组
        char[] ch = s.toCharArray();
        int n = s.length();
        int ans = 1;
        int l = 0;
        int same = 0;
        for (int r = 1; r < n; r++) {
            // 需要比较与前一个数是否相同
            if (ch[r] == ch[r - 1]) {
                same++;
            }
            // 表示出现了两次
            if (same > 1) {
                l++;
                while (ch[l] != ch[l - 1]) {
                    l++;
                }
                same = 1;
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$，使用了 ch 存储将字符串 s 转换为字符数组的变量，直接使用 String 的 charAt 即可减少空间复杂度