shortest-supersequence-lcci

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。

英文版：Cracking the Coding Interview，源自硅谷程序员的面试红宝书

LCCI

You are given two arrays, one shorter (with all distinct elements) and one longer. Find the shortest subarray in the longer array that contains all the elements in the shorter array. The items can appear in any order.

Return the indexes of the leftmost and the rightmost elements of the array. If there are more than one answer, return the one that has the smallest left index. If there is no answer, return an empty array.

Example 1:

<pre>
Input:
big = <code>[7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]</code>
Output: [7,10]</pre>

Example 2:

<pre>
Input:
big = <code>[1,2,3]
small = [4]</code>
Output: []</pre>

Note: 

<ul>
	<li><code>big.length&nbsp;&lt;= 100000</code></li>
	<li><code>1 &lt;= small.length&nbsp;&lt;= 100000</code></li>
</ul>

shortestSeq

Shortest Supersequence LCCI

Array

Hash Table

Sliding Window

假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。

返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。

示例 1：

<pre>
输入：
big = <code>[7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]</code>
输出：[7,10]</pre>

示例 2：

<pre>
输入：
big = <code>[1,2,3]
small = [4]</code>
输出：[]</pre>

提示：

<ul>
	<li><code>big.length&nbsp;&lt;= 100000</code></li>
	<li><code>1 &lt;= small.length&nbsp;&lt;= 100000</code></li>
</ul>