题目列表

题目列表：

应用

Leetcode 643. 子数组最大平均数 I

题目

643. 子数组最大平均数 I

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

解题思路

对于数组的区间求和，可以使用前缀和的思路求解。

对于区间长度固定的子数组，我们只需要枚举区间的右侧端点即可。

代码实现

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        int right = k;
        int windowSum = sum[k];
        while (right <= n) { // 注意：这里前缀和的范围是[1, n]
            windowSum = Math.max(windowSum, sum[right] - sum[right - k]);
            right++;
        }
        return windowSum * 1.0 / k;
    }
}

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

题目

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

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路

使用滑动窗口的思路，使用哈希表 \(window\) 记录窗口中字符的数量，每一个右指针移动的时候，对应的字符个数就增加 \(1\)，左指针移动时，就将移除窗口的字符数量减 \(1\)，字符数量减小到 \(0\)时，就将哈希表中对应字符的 \(key\) 删除。

代码实现

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        Map<Character, Integer> window = new HashMap<>();
        int maxLength = 0;
        int left = 0, right = 0;
        while (right < n) {
            Character tail = s.charAt(right);
            window.put(tail, window.getOrDefault(tail, 0) + 1);
            if (window.size() == right - left + 1) {
                maxLength = Math.max(maxLength, right - left + 1);
            }

            while (right - left + 1 > window.size()) {
                Character head = s.charAt(left);
                window.put(head, window.get(head) - 1);
                if (window.get(head).equals(0)) {
                    window.remove(head);
                }
                left++;
            }
            right++;
        }
        return maxLength;
    }
}

Leetcode 159. 至多包含两个不同字符的最长子串

题目

159. 至多包含两个不同字符的最长子串

给你一个字符串 s ，请你找出 至多 包含 两个不同字符 的最长子串，并返回该子串的长度。

示例 1：

输入：s = "eceba"
输出：3
解释：满足题目要求的子串是 "ece" ，长度为 3 。

解题思路

假设字符串 \(s\) 的长度为 \(n\)，维护两个指针 \(left\)、\(right\)，在移动右指针 \(right\) 的过程中，如果窗口中字符种类小于等于 \(2\) 时，就更新最大的窗口长度。

同时，只要窗口中的字符种类大于 \(2\) 就缩小左侧区间。

注意，目标字符串可能只有一种字符或者是空字符，所以，需要在小于等于 \(2\) 时，更新最大窗口的长度。

代码实现

class Solution {
    private static final int MAX = 2;

    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int n = s.length();
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int maxWindLength = 0;
        while (right < n) {
            Character tail = s.charAt(right);
            window.put(tail, window.getOrDefault(tail, 0) + 1);
            if (window.keySet().size() <= MAX) {
                maxWindLength = Math.max(maxWindLength, right - left + 1);
            }

            while (window.keySet().size() > MAX) {
                Character head = s.charAt(left);
                window.put(head, window.get(head) - 1);
                if (window.get(head).equals(0)) {
                    window.remove(head);
                }

                left++;
            }
            right++;
        }
        return maxWindLength;
    }
}

Leetcode 209. 长度最小的子数组

题目

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

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

解题思路

略。

代码实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        int left = 0, right = 0;
        int minSize = n + 1;
        while (right <= n) {
            while (left < right && sum[right] - sum[left] >= target) {
                int current = sum[right] - sum[left];
                if (current >= target) {
                    minSize = Math.min(minSize, right - left);
                }
                left++;
            }
            right++;
        }
        return minSize == n + 1 ? 0 : minSize;
    }
}