1. LeetCode 3 无重复字符的最长子串
方法1：滑动窗口 + 哈希
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> set = new HashSet<Character>();
int left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right)))
set.remove(s.charAt(left++));
ans = Math.max(ans, right - left + 1);
set.add(s.charAt(right));
}
return ans;
}
}
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
st = set(); left = ans = 0
for right, ch in enumerate(s):
while ch in st:
st.remove(s[left])
left += 1
ans = max(ans, right - left + 1)
st.add(ch)
return ans
2. LeetCode 1493 删掉一个元素以后全为1的最长子数组
方法1：滑动窗口
class Solution {
public int longestSubarray(int[] nums) {
int left = 0, ans = 0, cnt = 0; // 标记当前 0 的个数
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0)
cnt += 1;
while (cnt > 1) {
if (nums[left] == 0)
cnt -= 1;
left += 1;
}
// 保证[left , right]中只有一个 0
ans = Math.max(ans, right - left + 1);
}
return ans - 1;
}
}
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
cnt, left, ans = 0, 0, 0
for right, x in enumerate(nums):
if x == 0:
cnt += 1
while cnt > 1:
if nums[left] == 0:
cnt -= 1
left += 1
# 保证[left, right]中只有一个 0
ans = max(ans, right - left + 1)
return ans - 1 # 减去其中需要删除的一个元素
方法2：思维 + 前缀和
class Solution {
public int longestSubarray(int[] nums) {
int n = nums.length;
int[] prev = new int[n]; // 当前位置结尾前面连续 1 的个数
prev[0] = nums[0]; // 初始化
for (int i = 1; i < n; i++)
prev[i] = nums[i] == 1 ? prev[i - 1] + 1 : 0;
int[] next = new int[n]; // 当前位置结尾后面连续 1 的个数
next[n - 1] = nums[n - 1]; // 初始化
for (int i = n - 2; i >= 0; i--)
next[i] = nums[i] == 1 ? next[i + 1] + 1 : 0;
int ans = 0;
for (int i = 0; i < n; i++) { // 枚举要删除的位置
int prevS = i == 0 ? 0 : prev[i - 1];
int nextS = i == n - 1 ? 0 : next[i + 1];
ans = Math.max(ans, prevS + nextS);
}
return ans;
}
}
class Solution:
def longestSubarray(self, nums: List[int]) -> int:
n = len(nums)
pre = [nums[0]] * n; nxt = [nums[n - 1]] * n
for i in range(1, n): # 初始化 pre 数组
pre[i] = 0 if nums[i] == 0 else pre[i - 1] + 1
for i in range(n - 2, -1, -1):
nxt[i] = 0 if nums[i] == 0 else nxt[i + 1] + 1
ans = 0
for i in range(n):
preS = 0 if i == 0 else pre[i - 1]
nxtS = 0 if i == n - 1 else nxt[i + 1]
ans = max(ans, preS + nxtS)
return ans
3. LeetCode 2730 找到最长的半重复子字符串
方法1：滑动窗口
class Solution {
public int longestSemiRepetitiveSubstring(String s) {
int val = 0, left = 0, ans = 1; // 当只有一个字符时返回 1
for (int right = 1; right < s.length(); right++) {
if (s.charAt(right) == s.charAt(right - 1))
val += 1; // 相邻重复个数加 1
while (val > 1) {
if(s.charAt(left) == s.charAt(left + 1))
val -= 1;
left += 1;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
class Solution:
def longestSemiRepetitiveSubstring(self, s: str) -> int:
cnt, left, ans = 0, 0, 1
for right in range(1, len(s)):
if s[right - 1] == s[right]:
cnt += 1
while cnt > 1:
if s[left] == s[left + 1]:
cnt -= 1
left += 1
ans = max(ans, right - left + 1)
return ans
4. LeetCode 904 水果成篮
方法1：滑动窗口 + 哈希表
class Solution {
public int totalFruit(int[] fruits) {
// 标记区间数字出现次数
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// left：左端点 ans：最终答案
int left = 0, ans = 0;
for (int right = 0; right < fruits.length; right++) {
map.merge(fruits[right], 1, Integer::sum);
while (map.size() > 2) {
if (map.merge(fruits[left], -1, Integer::sum) == 0)
map.remove(fruits[left]);
left += 1;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
class Solution:
def totalFruit(self, fruits: List[int]) -> int:
cnt = Counter() # python的计数器
left, ans = 0, 0
for right, x in enumerate(fruits):
cnt[x] += 1 # 如果不存在会自动创建
while len(cnt) > 2:
cnt[fruits[left]] -= 1
if cnt[fruits[left]] == 0: # 需要手动删除
cnt.pop(fruits[left])
left += 1
ans = max(ans, right - left + 1)
return ans
5. LeetCode 1695 删除子数组的最大得分
方法1：滑动窗口 + 哈希表
class Solution {
public int maximumUniqueSubarray(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int left = 0, val = 0, ans = 0;
for (int right = 0; right < nums.length; right++) {
map.merge(nums[right], 1, Integer::sum);
val += nums[right];
while (map.get(nums[right]) > 1) {
map.merge(nums[left], -1, Integer::sum);
// 此处可以删除键值为 0 的键
val -= nums[left]; left++;
}
ans = Math.max(ans, val);
}
return ans;
}
}
class Solution:
def maximumUniqueSubarray(self, nums: List[int]) -> int:
cnt = Counter() # 统计每个数字出现的次数
left, val, ans = 0, 0, 0
for right, x in enumerate(nums):
cnt[x] += 1; val += x
while cnt[x] > 1:
cnt[nums[left]] -= 1
val -= nums[left]
# 此处可以删除个数为 0 的键
left += 1
ans = max(ans, val)
return ans
6. LeetCode 2958 最多 K 个重复元素的最长子数组
方法1：滑动窗口 + 哈希表
class Solution {
public int maxSubarrayLength(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int left = 0, ans = 0;
for (int right = 0; right < nums.length; right++) {
map.merge(nums[right], 1, Integer::sum);
while (map.get(nums[right]) > k) {
map.merge(nums[left], -1, Integer::sum);
// 此处可以删除键值为 0 的键
left++;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
class Solution:
def maxSubarrayLength(self, nums: List[int], k: int) -> int:
cnt = Counter() # 统计每个数字出现的次数
left, ans = 0, 0
for right, x in enumerate(nums):
cnt[x] += 1
while cnt[x] > k:
cnt[nums[left]] -= 1
# 此处可以删除个数为 0 的键
left += 1
ans = max(ans, right - left + 1)
return ans
7. LeetCode 1004 最大连续1的个数III
方法1：滑动窗口
class Solution {
public int longestOnes(int[] nums, int k) {
int cnt = 0, left = 0, ans = 0;
for (int right = 0; right < nums.length; right++) {
cnt += nums[right] == 0 ? 1 : 0;
while (cnt > k) {
cnt -= nums[left] == 0 ? 1 : 0;
left += 1;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
cnt, left, ans = 0, 0, 0
for rigth, x in enumerate(nums):
cnt += 1 if x == 0 else 0
while cnt > k:
cnt -= 1 if nums[left] == 0 else 0
left += 1
ans = max(ans, rigth - left + 1)
return ans
8. LeetCode 2024 考试的最大困扰度
方法1：滑动窗口
class Solution {
public int maxConsecutiveAnswers(String answerKey, int k) {
return Math.max(longest(answerKey, k, 'T'), longest(answerKey, k, 'F'));
}
public int longest(String s, int k, char ch) {
int cnt = 0, left = 0, ans = 0;
for (int right = 0; right < s.length(); right++) {
cnt += s.charAt(right) == ch ? 1 : 0;
while (cnt > k) {
cnt -= s.charAt(left) == ch ? 1 : 0;
left += 1;
}
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
class Solution:
def maxConsecutiveAnswers(self, answerKey: str, k: int) -> int:
return max(self.longest(answerKey, k, 'T'), self.longest(answerKey, k, 'F'))
def longest(self, s: str, k: int, ch: str) -> int:
cnt, left, ans = 0, 0, 0
for rigth, x in enumerate(s):
cnt += 1 if x == ch else 0
while cnt > k:
cnt -= 1 if s[left] == ch else 0
left += 1
ans = max(ans, rigth - left + 1)
return ans
9.