【编程笔记】数组元素的目标和·判断子序列

数组元素的目标和

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

数组下标从 0 开始。

请你求出满足 A[i]+B[j]=x的数对 (i,j)。数据保证有唯一解。

输入格式

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

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

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

数组元素的目标和思路

首先，这两个序列，使之维护某种次序，即判断两个有序序列中符合A[i]+B[j]=x的数对 (i,j)的操作。

同时，为了减少循环，采用双指针算法，即用两个指针来保证能遍历符合要求的所有数；

i指针从A数组的头开始，此时a[i]最小；

j指针从B数组的尾开始，此时b[j]最大；

当a[i] + b[j] 的值第一次小于x时，j指针的左边的数与a[i]相加一定比x小；那么只能增大a[i]的值，即令i 往后移一位;

自此开始反复循环,如果a[i] + b[j] 大于x，就相当于将j指针左移（减小b[j]）反之，就i指针右移（令a[i]数增大）

这样，一定可以保证每一个符合要求的两个数都能进入条件，即判断是不是和等于x。

时间复杂度为O(n+m) [j指针的移动与i指针的移动是分开的，因此两者无关，故不为O(n*m)]。

数组元素的目标和

给定一个长度为 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。

判断子序列思路

首先，两个序列需要维护某种次序，即，A顺次映射到B。

同时，两个序列，在确定匹配一定可以成功的时候，全部是有顺序的，符合双指针的单调性（不回头）的特点。

因此考虑双指针做法。

其次，A为B的子序列意味着，A可以顺次映射到B中，而非A无法顺次映射到B中。

举例，ace是abcde的子序列，但aec不是。

令i指针用来扫描a数组，令j指针用来扫描整个b数组。若发现a[i] == b[j]，则让i指针后移一位。

通过不断后移j指针，匹配成功后移动一位i指针，直到i == n，说明匹配成功。

给定一组匹配，使用双指针找到的是第一个不同的。

这样的好处就是，当存在一种匹配方式，这样使用双指针算法一定能够找出，证明的方法可以采用反证法。

时间复杂度为O(n)。

祝贺，新年快乐！