數(shù)組元素的目標(biāo)和

給定兩個(gè)升序排序的有序數(shù)組?A?和?B，以及一個(gè)目標(biāo)值?x。

數(shù)組下標(biāo)從?0?開始。

請你求出滿足?A[i]+B[j]=x的數(shù)對?(i,j)。數(shù)據(jù)保證有唯一解。

輸入格式

第一行包含三個(gè)整數(shù)?n,m,x，分別表示?A?的長度，B?的長度以及目標(biāo)值?x。

第二行包含?n?個(gè)整數(shù)，表示數(shù)組?A。

第三行包含?m?個(gè)整數(shù)，表示數(shù)組?B。

數(shù)組元素的目標(biāo)和思路

首先，這兩個(gè)序列，使之維護(hù)某種次序，即判斷兩個(gè)有序序列中符合A[i]+B[j]=x的數(shù)對?(i,j)的操作。

同時(shí)，為了減少循環(huán)，采用雙指針?biāo)惴?，即用兩個(gè)指針來保證能遍歷符合要求的所有數(shù)；

i指針從A數(shù)組的頭開始，此時(shí)a[i]最小；

j指針從B數(shù)組的尾開始，此時(shí)b[j]最大；

當(dāng)a[i] + b[j] 的值第一次小于x時(shí)，j指針的左邊的數(shù)與a[i]相加一定比x??；那么只能增大a[i]的值，即令i 往后移一位;

自此開始反復(fù)循環(huán),如果a[i] + b[j] 大于x，就相當(dāng)于將j指針左移（減小b[j]）反之，就i指針右移（令a[i]數(shù)增大）

這樣，一定可以保證每一個(gè)符合要求的兩個(gè)數(shù)都能進(jìn)入條件，即判斷是不是和等于x。

時(shí)間復(fù)雜度為O(n+m) [j指針的移動(dòng)與i指針的移動(dòng)是分開的，因此兩者無關(guān)，故不為O(n*m)]。

數(shù)組元素的目標(biāo)和

給定一個(gè)長度為?n?的整數(shù)序列?a1,a2,…,an?以及一個(gè)長度為?m?的整數(shù)序列?b1,b2,…,bm。

請你判斷?a?序列是否為?b?序列的子序列。

子序列指序列的一部分項(xiàng)按原有次序排列而得的序列，例如序列?{a1,a3,a5}是序列?{a1,a2,a3,a4,a5}的一個(gè)子序列。

輸入格式

第一行包含兩個(gè)整數(shù)?n,m。

第二行包含?n?個(gè)整數(shù)，表示?a1,a2,…,an。

第三行包含?m?個(gè)整數(shù)，表示?b1,b2,…,bm。

輸出格式

如果?a?序列是?b?序列的子序列，輸出一行?Yes。

否則，輸出?No。

判斷子序列思路

首先，兩個(gè)序列需要維護(hù)某種次序，即，A順次映射到B。

同時(shí)，兩個(gè)序列，在確定匹配一定可以成功的時(shí)候，全部是有順序的，符合雙指針的單調(diào)性（不回頭）的特點(diǎn)。

因此考慮雙指針做法。

其次，A為B的子序列意味著，A可以順次映射到B中，而非A無法順次映射到B中。

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

令i指針用來掃描a數(shù)組，令j指針用來掃描整個(gè)b數(shù)組。若發(fā)現(xiàn)a[i] == b[j]，則讓i指針后移一位。

通過不斷后移j指針，匹配成功后移動(dòng)一位i指針，直到i == n，說明匹配成功。

給定一組匹配，使用雙指針找到的是第一個(gè)不同的。

這樣的好處就是，當(dāng)存在一種匹配方式，這樣使用雙指針?biāo)惴ㄒ欢軌蛘页觯C明的方法可以采用反證法。

時(shí)間復(fù)雜度為O(n)。

祝賀，新年快樂！