ACW06-双指针算法

ACW Practice 06: The double index

Posted by qingshan on May 3, 2019

ACW双指针算法01:799. 最长连续不重复子序列

给定一个长度为 n 的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。

输入格式 第一行包含整数 n。

第二行包含 n 个整数(均在 0∼1e5 范围内),表示整数序列。

输出格式 共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。

数据范围 1≤n≤1e5

1
2
3
4
5
输入样例:
5
1 2 2 3 5
输出样例:
3

思路:双指针

设置一个字典,key 为整数序列的值。如果对应的值为曾经出现的次数。如果 j<=i 且 d[a[j]]出现不止一次,说明有重复,j 指针后移,并将值减一(重置),直到 d[a[j]]为 1。说明符合题意:不重复区间。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main():
    n = 5
    a = [1,2,2,3,5]

    i=j=res=0
    d = dict()

    while i<n:
        if d.get(a[i]) is None:
            d[a[i]] = 1
        else:
            d[a[i]] += 1
        
        while j<=i and d[a[j]] > 1:
            d[a[j]] -= 1
            j+=1

        i+=1
        res = max(res, i-j+1)
        
    print(res)

ACW双指针算法02:800. 数组元素的目标和

给定两个升序排序的有序数组 A 和 B,以及一个目标值 x。

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x 的数对 (i,j)。

数据保证有唯一解。

输入格式 第一行包含三个整数 n,m,x,分别表示 A 的长度,B 的长度以及目标值 x。

第二行包含 n 个整数,表示数组 A。

第三行包含 m 个整数,表示数组 B。

输出格式 共一行,包含两个整数 i 和 j。

数据范围 数组长度不超过 1e5。 同一数组内元素各不相同。 1≤数组元素≤1e9

1
2
3
4
5
6
输入样例:
4 5 6
1 2 4 7
3 4 6 8 9
输出样例:
1 1

思路:双指针

因为AB是单调递增数列, 所以 AB 的解位置一定有最大值。那么从 A 的第一个数,B 的最后一个数开始。如果j>0 and A[i] + B[j] >x,则 j往前移动一位,直到A[i] + B[j]<=x,然后把 A 的位置往后移动。直到A[i] + B[j]==x

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def main():
    n,m,x = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    i=0 # i 指向 n 数组的第一个元素
    j=m-1 # j 指向m 数组的最后一个元素

    while i<n:
        while A[i] + B[j] > x and j>0:
            j-=1 # 从 m 数组最后一个元素往前找

        if A[i] + B[j] == x:
            print(i, j)
            return # 找到后退出程序

        i+=1 # 从 A 数组第一个元素开始

if __name__ == "__main__":
    main()


ACW双指针算法03: 2816. 判断子序列

给定一个长度为 n 的整数序列 a1,a2,…,an 以及一个长度为 m 的整数序列 b1,b2,…,bm。

请你判断 a 序列是否为 b 序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列,例如序列 {a1,a3,a5} 是序列 {a1,a2,a3,a4,a5} 的一个子序列。

输入格式 第一行包含两个整数 n,m。

第二行包含 n 个整数,表示 a1,a2,…,an。

第三行包含 m 个整数,表示 b1,b2,…,bm。

输出格式 如果 a 序列是 b 序列的子序列,输出一行 Yes。

否则,输出 No。

数据范围 1≤n≤m≤105, −1e9≤ai,bi≤1e9

1
2
3
4
5
6
输入样例:
3 5
1 3 5
1 2 3 4 5
输出样例:
Yes

思路:双指针

a 序列是短的序列,它的指针仅当元素在 b 中找到时候,才往右移;b 是长的序列,它的指针每次都后移。停止条件为其中一个指针移到尾。如果 a 的指针等于 a 的长度,说明 a 是 b 的子序列,否则不是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def main():
    n, m = list(map(int, input().split()))
    
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    i=j=0
    while i<n and j<m:
        if A[i] == B[j]:
            i+=1
        j+=1
        
    if i == n: print("Yes")
    else:print("No")
    
if __name__ == "__main__":
    main()