同向双指针 和 滑动窗口
汇总了一下滑动窗口、同向双指针的一些题目，题目比较简单，使用同方向的双指针遍历数组即可出结果。
一般我们左右端点指针为 left 和 right ，枚举 right即可。
代码使用python语言，一般将其归纳如下：
# 设定左端点
left = 0
# 枚举右端点
for right, item in enumerate(array):
209. 长度最小的子数组
Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return 0 instead.
Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: The subarray [4,3] has the minimal length under the problem constraint.
Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1
Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0
Constraints:
Follow up: If you have figured out the 
solution, try coding another solution of which the time complexity is 
.
这题一拿到肯定觉得很简单，直接暴力，嵌套两个for循环遍历记录最小长度就行了。
但是这样时间复杂度是O(n2)O(n^2)O(n2)，我们能否优化一下？
题目有个关键，正整数 positive integers。
因为正整数，所以你的子数组和必定是大于0的。
如果
[l,r]和是大于target的，那[l,r+1]...之后的也是大于target的，我们就不用管了。你可以写成：
for l in range(len(nums)): for r in range(l+1,len(nums)): if sum([l,r+1]) > target: ans = min(ans,r-l+1) break也可以使用双指针进一步优化代码
时间复杂度
，空间复杂度
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
ans = len(nums) + 1
left = 0
s = 0
for right, n in enumerate(nums):
s += n
while s >= target:
ans = min(ans, right - left + 1)
s -= nums[left]
left += 1
return ans if ans <= len(nums) else 0
713. 乘积小于 K 的子数组
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than **k.
Example 1:
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are: [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6] Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Example 2:
Input: nums = [1,2,3], k = 0
Output: 0
Constraints:
这个题目的问题在于怎么求子串的数量，在本题目中
[l,r],[l+1,r],...,[r,r]都是[l,r]的子数组，所以数量其实是
时间复杂度
，空间复杂度
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
mul = 1
left = 0
ans = 0
for right,n in enumerate(nums):
mul *= n
while mul >= k:
mul /= nums[left]
left += 1
ans += right - left +1
# [l,r],[l+1,r],...,[r,r]都是[l,r]的子数组
return ans
3. 无重复字符的最长子串
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
- s consists of English letters, digits, symbols and spaces.
借助字典的话时间复杂度
，空间复杂
（ascii码表的长度
我比较懒，不借助字典了。
时间复杂度
，空间复杂
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
maxLength = 0
left=0
for right,c in enumerate(s):
while c in s[left:right]:
left += 1
maxLength = max(maxLength,right - left +1)
return maxLength
1004. 最大连续1的个数 III
Given a binary array nums and an integer k, return the maximum number of consecutive 1 's in the array if you can flip at most k 0's.
Example 1:
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
Example 2:
Input: nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], k = 3
Output: 10
Explanation: [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.
提示：
题目让你反转0为1，最多可以反转k次，让你找出最长的1的字串。
转换一下思路，这一题可以转换为“当子串内的0个数小于k的时候，最长子串是多少”
这么一想，题目是不是又回到了第一题。
时间复杂度
，空间复杂
class Solution:
def longestOnes(self, nums: List[int], k: int) -> int:
left = 0
maxLen = 0
count0 = 0
for right, n in enumerate(nums):
if n == 0:
count0 += 1
if count0 <= k:
maxLen = max(maxLen, right - left + 1)
while count0 > k:
while nums[left]:
left += 1
left += 1
count0 -= 1
return maxLen
起初我是上边这么写的，现在我是下边这么写的了。逻辑判断都不用了。👍我直呼牛蛙。
left = 0
maxLen = 0
count0 = 0
for right, n in enumerate(nums):
count0 += 1 - n
while count0 > k:
count0 -= 1 - nums[left]
left += 1
maxLen = max(maxLen, right - left + 1)
return maxLen
1234. 替换子串得到平衡字符串
You are given a string s of length n containing only four kinds of characters: 'Q', 'W', 'E', and 'R'.
A string is said to be balanced if each of its characters appears n / 4 times where n is the length of the string.
Return the minimum length of the substring that can be replaced with any other string of the same length to make s balanced. If s is already balanced, return 0.
Example 1:
Input: s = "QWER"
Output: 0
Explanation: s is already balanced.
Example 2:
Input: s = "QQWE"
Output: 1
Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced.
Example 3:
Input: s = "QQQW"
Output: 2
Explanation: We can replace the first "QQ" to "ER".
Constraints:
- n is a multiple of 4.
- s contains only 'Q', 'W', 'E', and 'R'.
这题目比较绕让你替换字母，最终整个字符串中QWER数量都相等，并且QWER数量都是字符串的四分之一。
窗口就是你要替换的最小字串。
窗口外的每个字母出现次数大于
n/4的话，你怎么调整都不可能让字符串平衡的。所以只有窗口外的字母出现次数都小于
n/4，你才可以调整窗口内的字符，让其成为平衡字符串。在这我掉坑里了，想着要不要判断窗口内的待调整字符和窗口外缺失的字符数量一样。
没必要考虑这个问题，题目中设定的就是长度是4的整数，窗口内外加起来必定是n，😶
class Solution:
def balancedString(self, s: str) -> int:
appear = len(s) // 4
count = Counter(s)
# 所有的都符合条件
if all(count[i] == appear for i in 'QWER'):
return 0
left = 0
ans = len(s) + 1
for right,c in enumerate(s):
count[c] -= 1
while all(count[i] <= appear for i in 'QWER'):
ans = min(ans,right-left+1)
count[s[left]] += 1
left += 1
return ans
1658. 将 x 减到 0 的最小操作数
You are given an integer array nums and an integer x. In one operation, you can either remove the leftmost or the rightmost element from the array nums and subtract its value from x. Note that this modifies the array for future operations.
Return the minimum number of operations to reduce x to exactly 0 if it is possible, otherwise, return -1.
Example 1:
Input: nums = [1,1,4,2,3], x = 5
Output: 2
Explanation: The optimal solution is to remove the last two elements to reduce x to zero.
Example 2:
Input: nums = [5,6,7,8,9], x = 4
Output: -1
Example 3:
Input: nums = [3,2,20,1,1,3], x = 10
Output: 5
Explanation: The optimal solution is to remove the last three elements and the first two elements (5 operations in total) to reduce x to zero.
Constraints:
题目写的从两边移除元素，从哪边移除都行，数组也是无序的。看这个题目第一反应是用双向队列啊，但是要用双向队列的话你就需要进行很多逻辑判断。
所以这时候考虑一下正难则反
移除两边的数，使之和为
x，寻找最小操作次数等价于：找最大连续子串，和为
sum(nums)-x
时间复杂度
，空间复杂
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
target = sum(nums) - x
if target < 0: # 所有的加起来也没x大
return -1
left = 0
s = 0
maxlen = -1 # 初始设定为 -1，防止出现中间子串为0的现象
for right,n in enumerate(nums):
s += n
while s > target:
s -= nums[left]
left += 1
if s == target:
maxlen = max(maxlen,right-left+1)
return len(nums) - maxlen if maxlen else -1
转载自:https://juejin.cn/post/7220253332420542520