同向双指针

2026-01-13

1. 长度最小的子数组

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

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



- 思路：

 - 暴力求解：遍历左端点或者右端点，以右端点为例。


  # 第一次遍历以2为右端点
  2 -> 小于7，扩大
  左边没有数了，无法扩大，说明以2为右端点无解，进行下一次迭代

# 第二次迭代，以3为右端点
3 -> 小于7，扩大
2,3 -> 小于7，扩大
左边没有数了，无法扩大，说明以3为右端点无解，进行下一次迭代

# 
1 -> 小于7，扩大
3,1 -> 小于7，扩大
2,3,1 -> 小于7，扩大
无解

# 
2 -> 小于7，扩大
1,2 -> 小于7，扩大
3,1,2 -> 小于7，扩大
2,3,1,2 -> 大于7，说明以2为右端点，得到的解为4

#...
1
2
3

- 优化求解，利用都是正数的性质，还是遍历右端点


# 第一次遍历以2为右端点
2 -> 小于7，扩大
左边没有数了，无法扩大，说明以2为右端点无解，进行下一次迭代

# 第二次迭代，以3为右端点
xxxxx 3 -> 小于7，扩大
上一步迭代得到的全串为2，直接在此基础上向右扩展右端点
2,3 -> 小于7，说明在第一次的全串(2)基础上扩展右端点(3)还是无法满足，进一步扩展右端点
2,3,1 -> 小于7，说明在第一次的全串(2,3)基础上扩展右端点(1)还是无法满足，进一步扩展右端点
2,3,1,2 -> 大于7，说明以2为右端点可以获得一个解，为了最短，尝试将左端点右移，发现3,1,2不满足，因此左端点不动，记录该长度为4，进一步扩展右端点
2,3,1,2,4 -> 由于上一步的结果大于7，这次右端点扩展了一个数，肯定大于7，需要缩短（固定右端点）以找到最短序列，尝试右移左端点，
3,1,2,4 -> 大于7，记录左边界更新（3），再次尝试右移左端点
1,2,4 -> 大于等于7，记录该长度为3，更新最优解，记录左边界更新（1），再次尝试右移左端点
2,4 -> 小于7，说明以4为右端点的情况已经遍历全了，回退一步：1，2，4，进一步扩展右端点

1，2，4，3 -> 由于上一步的结果大于7，这次右端点扩展了一个数，肯定大于7，需要缩短（固定右端点）以找到最短序列
2，4，3 -> 大于等于7，记录该长度为3，更新最优解，记录左边界更新（2），再次缩短
4，3 -> 大于等于7，记录该长度为2，更新最优解，记录左边界更新（4），再次缩短
3 -> 小于7，说明以3为右端点的情况已经遍历全了，回退一步：3，4，进一步扩展右端点

# 遍历完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

```python
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        res = n+1
        sum = 0
        left = 0
        for right,x in enumerate(nums):
            sum += x
            while sum - nums[left] >= target:
                sum  -= nums[left]
                left += 1                 
            res = min(res, right-left+1) if sum >= target else res
           
        return res if res <=n else 0

2. 乘积小于K的子数组

（713）给你一个整数数组 nums和一个整数k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
```python
class Solution:
   def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
       if k <=1:
           return 0
       ans,left = 0,0
       # 遍历右端点
       prod = 1
       for right,x in enumerate(nums):
           prod *= x
           while prod >= k and left <= right:
               prod /= nums[left]
               left += 1
           ans += right - left + 1
       return ans

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

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

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。
1
2
3
4
5
6
7
8
9
10
11
12
13

```python
class Solution:
   def lengthOfLongestSubstring(self, s: str) -> int:
       ans,left = 0,0
       dic = {}
       for right,x in enumerate(s):
           dic[x] = dic.get(x,0) + 1
           while dic[x] > 1:
               dic[s[left]] -=1
               left += 1
           ans = max(ans, right - left + 1)
       return ans