思路
双指针通常在滑动区间算法中使用,与KMP尽可能的复用已计算的信息思想一致。
先确定可能的边界条件,预估充分出现在计算过程中动态调整指针区间,区间大小,移动求最大最小,至少要遍历一次给定的目标区,但可以M+N就不必M*N
最大连续1的个数
给定一个二进制数组, 计算其中最大连续1的个数。输入数组的长度是正整数,且不超过 10,000。
输入
: [1,1,0,1,1,1]
输出
: 3
解释
: 开头的两位和最后的三位都是连续
1,所以最大连续
1的个数是
3.
算法
func findMaxConsecutiveOnes(nums
[]int) int {
j
,rs
:=0,0
for i
:=0;i
<len(nums
);i
++ {
if nums
[i
]==1 {
rs
= Max(rs
,i
-j
+1)
}else{
j
=i
+1
}
}
return rs
}
分析
计算连续数个数 ,知道连续首j 尾 i 索引,i-j+1即为其个数 假定当前索引为非连续子索引,则动态的将首索引指向 i+1,即可确定当前,不可确定下一个,则进行下一个判断
长度最小子数组
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
输入:s
= 7, nums
= [2,3,1,2,4,3]
输出:
2
解释:子数组
[4,3] 是该条件下的长度最小的子数组。
代码
func minSubArrayLen(s
int, nums
[]int) int {
if len(nums
)==0 {
return 0
}
left
,right
,sum
,subLen
:= 0,0,0,math
.MaxInt64
for right
< len(nums
) {
sum
+=nums
[right
]
for sum
>= s
{
subLen
= Min(subLen
, right
-left
+1)
sum
-=nums
[left
]
left
++
}
right
++
}
if subLen
== math
.MaxInt64
{
return 0
}
return subLen
}
关键
求和结果复用,考虑例外情况将限制条件s 作为限定区间大小的参与条件合理调整滑动区间的左右边界将计算的可能最大数作为不可预计初始化最小长度值,使用比较记录总有一个指针会走完全程