最长和谐子序列、重复的DNA序列、找到字符串中所有字母异位词、滑动窗口最大值、最小区间。每题做详细思路梳理，配套Python&Java双语代码， 2024.03.06 可通过leetcode所有测试用例。

594. 最长和谐子序列

        和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

        现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

        数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

 

示例 1：

输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]
示例 2：

输入：nums = [1,2,3,4]
输出：2
示例 3：

输入：nums = [1,1,1,1]
输出：0
 

提示：

1 <= nums.length <= 2 * 104
-109 <= nums[i] <= 109

 

 

解题思路

        对于这个题目，尽管看起来像是需要使用滑动窗口技术，但实际上它更适合使用哈希表来解决。原因在于我们需要追踪数组中每个元素的出现次数，并快速计算最大值和最小值之差为1的子序列长度。滑动窗口技术更适合于连续子数组问题，而这里的子序列不要求连续，因此直接使用滑动窗口技术可能不是最优解。

1. 使用哈希表记录数组中每个数字出现的次数。
2. 遍历哈希表，对于哈希表中的每个键值对(num, count)，检查num + 1是否也在哈希表中。
3. 如果num + 1也在哈希表中，那么count + hashMap[num + 1]就是以num和num + 1为元素的和谐子序列的长度。
4. 更新记录的最长和谐子序列长度。

完整代码

Java

public class Solution {
    public int findLHS(int[] nums) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();  // 创建HashMap用于存储每个数字及其出现次数
        for (int num : nums) {
            // 如果num已存在于HashMap中，则增加其计数；否则，添加num到HashMap并设置计数为1
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        int maxLength = 0;  // 初始化最长和谐子序列长度为0
        for (int key : hashMap.keySet()) {
            // 检查key+1是否也存在于HashMap中
            if (hashMap.containsKey(key + 1)) {
                // 如果存在，则计算包含key和key+1的和谐子序列长度，并更新最长长度
                maxLength = Math.max(maxLength, hashMap.get(key) + hashMap.get(key + 1));
            }
        }
        return maxLength;  // 返回最长和谐子序列长度
    }
}

Python

class Solution:
    def findLHS(self, nums: List[int]) -> int:
        hashMap = Counter(nums)  # 使用Counter统计nums中每个数字的出现次数
        maxLength = 0  # 初始化最长和谐子序列长度为0
        for key in hashMap:
            # 检查key+1是否也在Counter对象中
            if key + 1 in hashMap:
                # 如果存在，则计算包含key和key+1的和谐子序列长度，并更新最长长度
                maxLength = max(maxLength, hashMap[key] + hashMap[key + 1])
        return maxLength  # 返回最长和谐子序列长度

187. 重复的DNA序列

 

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

 

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
 

提示：

0 <= s.length <= 105
s[i]=='A'、'C'、'G' or 'T'

 

解题思路

        我们可以使用滑动窗口加哈希表的方式来解决。我们将滑动窗口的大小设置为10，然后在字符串s上滑动这个窗口，同时使用哈希表来记录每个长度为10的子字符串出现的次数。当我们发现某个子字符串的出现次数超过1时，就将其加入到结果中。

1. 初始化一个空的哈希表hashMap来存储每个长度为10的子字符串及其出现的次数，以及一个空集合result来存储结果。
2. 遍历字符串s，对于每个起始位置i，提取长度为10的子字符串sub。
3. 将sub加入到哈希表中，如果sub已经在哈希表中，则增加其计数。
4. 如果sub的计数刚好为2（即此前已经出现过一次），将其添加到结果集合中。
5. 返回结果集合中的所有元素。

完整代码

Java

public class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        HashMap<String, Integer> hashMap = new HashMap<>();  // 存储每个子字符串及其出现次数
        List<String> result = new ArrayList<>();  // 存储结果
        
        for (int i = 0; i <= s.length() - 10; i++) {
            String sub = s.substring(i, i + 10);  // 提取长度为10的子字符串
            hashMap.put(sub, hashMap.getOrDefault(sub, 0) + 1);  // 更新哈希表
            
            // 如果子字符串出现次数为2，则添加到结果中
            if (hashMap.get(sub) == 2) {
                result.add(sub);
            }
        }
        
        return result;  // 返回结果
    }
}

Python

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        seen, repeated = set(), set()  # 初始化seen和repeated集合
        for i in range(len(s) - 9):  # 遍历字符串，确保子字符串长度为10
            sequence = s[i:i+10]  # 获取当前位置的长度为10的子字符串
            if sequence in seen:  # 检查子字符串是否已存在于seen集合中
                repeated.add(sequence)  # 如果是，则添加到repeated集合中
            else:
                seen.add(sequence)  # 否则，将其添加到seen集合中
        return list(repeated)  # 将repeated集合转换为列表并返回

438. 找到字符串中所有字母异位词

 

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

 

示例 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" 的异位词。
 

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

 

解题思路

        我们可以使用滑动窗口技术配合哈希表来解决。这个方法有效地跟踪了窗口内各字符的出现频次，并将其与目标字符串p的字符频次进行比较。

1. 初始化：创建两个哈希表，sCount和pCount，分别用于存储当前窗口内的字符频次和字符串p的字符频次。还需要一个结果列表result来存储所有异位词子串的起始索引。
2. 填充pCount：遍历字符串p，更新pCount哈希表，记录每个字符的出现次数。
3. 滑动窗口：使用两个指针，start和end，代表窗口的起始和结束位置。窗口大小与字符串p的长度相同。
4. 窗口扩展：移动end指针，每次移动时，在sCount中更新end指针指向的字符频次。如果end-start+1小于p的长度，继续移动end指针。
5. 窗口收缩与检查：一旦窗口大小与p的长度相同，比较sCount和pCount：
   • 如果两个哈希表相等，意味着找到了一个异位词的起始索引，将start添加到结果列表result中。
   • 不管是否找到异位词，都需要从sCount中移除start指针指向的字符（即窗口左边界的字符），然后移动start指针，以收缩窗口并进行下一轮检查。
6. 返回结果：返回结果列表result。

完整代码

Java

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) {
            return result;  // 如果s的长度小于p的长度，直接返回空列表
        }

        HashMap<Character, Integer> pCount = new HashMap<>();
        HashMap<Character, Integer> sCount = new HashMap<>();

        // 填充pCount哈希表
        for (char ch : p.toCharArray()) {
            pCount.put(ch, pCount.getOrDefault(ch, 0) + 1);
        }

        int start = 0, end = 0;
        while (end < s.length()) {
            char endChar = s.charAt(end);
            sCount.put(endChar, sCount.getOrDefault(endChar, 0) + 1);

            // 如果窗口大小等于p的长度
            if (end - start + 1 == p.length()) {
                if (sCount.equals(pCount)) {
                    result.add(start);  // 添加当前窗口的起始索引到结果列表
                }

                char startChar = s.charAt(start);
                // 从sCount中移除窗口左边界的字符
                sCount.put(startChar, sCount.get(startChar) - 1);
                if (sCount.get(startChar) == 0) {
                    sCount.remove(startChar);  // 如果字符频次为0，从计数器中删除
                }
                start++;  // 收缩窗口
            }
            end++;  // 扩展窗口
        }

        return result;
    }
}

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):  # 如果s的长度小于p的长度，直接返回空列表
            return []

        pCount = Counter(p)  # 计算字符串p中各字符的频次
        sCount = Counter()  # 初始化s的字符频次计数器

        result = []  # 存储结果的列表
        for i in range(len(s)):
            sCount[s[i]] += 1  # 更新窗口内字符的频次
            if i >= len(p):
                if sCount[s[i - len(p)]] == 1:
                    del sCount[s[i - len(p)]]  # 如果字符频次为1，从计数器中删除
                else:
                    sCount[s[i - len(p)]] -= 1  # 否则减少字符频次

            if sCount == pCount:  # 如果当前窗口的字符频次与p的字符频次相同
                result.append(i - len(p) + 1)  # 添加当前窗口的起始索引到结果列表

        return result

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置              最大值
---------------                      -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2：

输入：nums = [1], k = 1
输出：[1]
 

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

解题思路

        这个问题可以通过维护一个双端队列（deque）来有效地解决。双端队列能够从两端以常数时间复杂度进行插入和删除操作。在这个问题中，我们可以利用双端队列来维护滑动窗口内的最大值。

1. 初始化：创建一个空的双端队列（deque）dq，和一个用于存储结果的列表max_values。
2. 遍历数组：遍历给定数组nums的每个元素，对于每个元素，执行以下操作：
   • 维护双端队列：
     • 如果双端队列不为空且队列头部的元素（最左侧元素）不在当前滑动窗口内（即索引小于当前元素索引 - 窗口大小），则从队列头部移除该元素。
     • 从队列尾部开始，移除所有小于当前元素nums[i]的元素，因为它们不可能是当前滑动窗口的最大值。
   • 将当前元素索引添加到双端队列尾部。
   • 记录最大值：一旦形成了大小为k的滑动窗口（即i >= k - 1），将双端队列头部的元素（当前窗口的最大值）添加到结果列表max_values中。
3. 返回结果：遍历完成后，返回max_values列表。

完整代码

Java

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> dq = new LinkedList<>();  // 初始化双端队列
        ArrayList<Integer> maxValues = new ArrayList<>();  // 初始化结果列表

        for (int i = 0; i < nums.length; i++) {
            // 移除不在窗口内的元素
            while (!dq.isEmpty() && dq.peek() < i - k + 1) {
                dq.poll();
            }

            // 移除所有小于当前元素的元素
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }

            dq.offer(i);  // 将当前元素索引添加到队列尾部

            // 当窗口大小达到k时，记录当前窗口的最大值
            if (i >= k - 1) {
                maxValues.add(nums[dq.peek()]);
            }
        }

        // 将结果列表转换为数组并返回
        int[] result = new int[maxValues.size()];
        for (int i = 0; i < maxValues.size(); i++) {
            result[i] = maxValues.get(i);
        }
        return result;
    }
}

Python

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = deque()  # 初始化双端队列
        max_values = []  # 初始化结果列表

        for i in range(len(nums)):
            # 移除不在窗口内的元素
            while dq and dq[0] < i - k + 1:
                dq.popleft()
            
            # 移除所有小于当前元素的元素
            while dq and nums[dq[-1]] < nums[i]:
                dq.pop()
            
            dq.append(i)  # 将当前元素索引添加到队列尾部

            # 当窗口大小达到k时，记录当前窗口的最大值
            if i >= k - 1:
                max_values.append(nums[dq[0]])
        
        return max_values

632. 最小区间

        你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

        我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

 

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]
 

提示：

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-10^5 <= nums[i][j] <= 10^5
nums[i] 按非递减顺序排列

 

解题思路

        这个问题可以通过使用最小堆（优先队列）来有效解决。核心思想是维护一个包含来自每个列表的最小元素的堆，同时跟踪当前的最小区间。我们需要确保当前堆中包含来自每个列表的至少一个元素，以此来找到包含至少一个元素的最小区间。

1. 初始化：创建一个最小堆（优先队列），用于存储每个列表中的元素及其来源列表的索引和元素在列表中的索引。同时，初始化一个变量max来跟踪堆中的最大元素。
2. 填充堆：将每个列表的第一个元素加入堆中，并更新max为这些元素的最大值。
3. 寻找最小区间：
   • 初始化最小区间的左右端点minRangeLeft和minRangeRight，初始设为无穷大和无穷小。
   • 当堆的大小等于列表的数量（即堆中包含来自每个列表的至少一个元素）时，循环进行以下操作：
     • 弹出堆顶元素（当前最小元素），记录其值和来源信息。
     • 更新当前最小区间：如果当前区间比已记录的最小区间小，更新minRangeLeft和minRangeRight。
     • 如果当前最小元素的来源列表中还有更多元素，将下一个元素加入堆中，并更新max。
4. 返回结果：返回最小区间[minRangeLeft, minRangeRight]。

完整代码

Java

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // 最小堆，按元素的值排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int minRange = Integer.MAX_VALUE, start = -1, end = -1, max = Integer.MIN_VALUE;
        
        // 初始化堆，加入每个列表的第一个元素
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            pq.offer(new int[]{val, i, 0});
            max = Math.max(max, val);
        }

        while (pq.size() == nums.size()) {
            int[] curr = pq.poll();
            int currVal = curr[0], row = curr[1], col = curr[2];
            // 更新最小区间
            if (max - currVal < minRange || (max - currVal == minRange && currVal < start)) {
                minRange = max - currVal;
                start = currVal;
                end = max;
            }
            // 如果当前元素的列表中还有更多元素，将下一个元素加入堆
            if (col + 1 < nums.get(row).size()) {
                currVal = nums.get(row).get(col + 1);
                pq.offer(new int[]{currVal, row, col + 1});
                max = Math.max(max, currVal);
            }
        }

        return new int[]{start, end};
    }
}

Python

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        # 初始化最小堆
        min_heap = []
        # 记录堆中所有元素的最大值
        max_val = float('-inf')
        # 遍历nums，将每个列表的第一个元素及其索引信息加入堆中
        for i, sublist in enumerate(nums):
            heapq.heappush(min_heap, (sublist[0], i, 0))
            max_val = max(max_val, sublist[0])
        
        # 初始化区间的起始和结束值
        start, end = float('-inf'), float('inf')

        while len(min_heap) == len(nums):
            # 弹出当前最小元素
            min_val, row, col = heapq.heappop(min_heap)
            # 如果当前的[start, end]区间大于新的可能区间，则更新区间
            if max_val - min_val < end - start:
                start, end = min_val, max_val
            # 如果弹出的元素所在的行还有更多元素，将下一个元素加入堆中
            if col + 1 < len(nums[row]):
                next_val = nums[row][col + 1]
                heapq.heappush(min_heap, (next_val, row, col + 1))
                # 更新堆中所有元素的最大值
                max_val = max(max_val, next_val)

        return [start, end]