共计 2267 个字符，预计需要花费 6 分钟才能阅读完成。
一、287. 寻找反复数
给定一个蕴含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包含 1 和 n），可知至多存在一个反复的整数。假如只有一个反复的整数，找出这个反复的数。
1、HashMap
在没有其它附加条件的状况下，读者第一工夫会想到通过 HashMap 来记录呈现过的数字，从而找到反复数：
上述实现代码的工夫复杂度和空间复杂度都为 O(n)，如果只容许应用 O(1) 的空间复杂度，该如何解决这道题目呢？
2、Binary Search
这种条件下，最容易想到的就是通过两重循环暴力搜寻以后数字是否与前面的数字反复的办法来解决，然而这种计划的工夫复杂度为 O(n^2)，既然波及到了搜寻，就能够尝试通过二分搜索算法将工夫复杂度升高到 O(nlogn)。
依据后面的刷题教训，能够很容易地找出有序数组：1 到 n 的递增整数序列。
接下来的难点就是通过反复数的个性来确定下一轮搜寻区间是落在左半区间还是右半区间：
- 首先须要遍历 nums 数组，获取不大于以后两头数的数字的个数；
- 如果个数大于两头数，那么下一轮搜寻区间落在左半区间；
- 如果个数小于两头数，那么下一轮搜寻区间落在右半区间；
二、209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s，找出该数组中满足其和 ≥ s 的长度最小的间断子数组。如果不存在符合条件的间断子数组，返回 0。
1、Binary Search
这道题目中的有序数组不太好找，须要用到一个技巧：结构前缀和数组。
nums = [2, 3, 1, 2, 4, 3]
# 前缀和
sums = [0, 2, 5, 6, 8, 12, 15]从而上述示例中能够发现前缀和数组是一个有序数组，那么对于任意 i 到 j 的间断子数组之和，能够通过 sums[j+1] – sums[i] 求出。
并且依据前缀和的差值与 s 的比拟，能够判断满足条件的间断子数组的终止下标落在哪个区间内。
参考视频：传送门
通过前缀和对数组的预处理以及二分搜索算法，工夫复杂度为 O(nlogn)。
2、Two Points
除了上述二分搜索算法的解决办法之外，可能最简略暴力的办法就是通过嵌套循环找出长度最小的间断子数组，然而这种办法的工夫复杂度为 O(n^2)，有没有办法将其升高到 O(n) 的工夫复杂度呢？。
这里就要提及一下 滑动窗口算法，它罕用于解决间断子元素问题，将嵌套循环问题转化为单循环问题。
在本题中，通过头指针和尾指针保护以后间断子数组的和值窗口：
- 以后窗口的和值大于 s，那么头指针向后挪动一位；
- 以后窗口的和值小于 s，那么尾指针向后挪动一位；
三、153. 寻找旋转排序数组中的最小值
假如依照升序排序的数组在事后未知的某个点上进行了旋转。(例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。请找出其中最小的元素。你能够假如数组中不存在反复元素。
这一类型的题目在 Easy 中也呈现过，如：【852. 山脉数组的峰顶索引】和【162. 寻找峰值】。
本题中，本来的递增数组被转化成蕴含两个递增序列的数组，并且其中无反复元素，那么就能够得出：第一个递增数组中的任意一个元素都大于第二个递增数组中的元素。
有了这一要害信息，对于任一两头数，都能够将其与以后搜寻区间的最初一个元素相比拟，从而晓得以后两头数在哪一个递增序列上，而所求的最小值存在于第二个递增序列的头部，那么一直将搜寻区间往这一方向膨胀，即可失去最小值：
四、33. 搜寻旋转排序数组
假如依照升序排序的数组在事后未知的某个点上进行了旋转。(例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜寻一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1。你能够假如数组中不存在反复的元素。你的算法工夫复杂度必须是 O(log n) 级别。
这道题是【153. 寻找旋转排序数组中的最小值】的进阶题型。
在 153 中，只须要将搜寻区间一直向第二个递增区间膨胀，即可失去最小值。而本题中的目标值的地位并不确定，所以在每次确定搜寻区间时，须要思考很多种状况：
- 如果以后搜寻区间只落在一个递增区间上，那么和个别的解决办法没什么同样；
- 如果以后搜寻区间横跨两个递增区间，那么就须要依据两头数在第一个递增区间还是第二个递增区间上别离解决；
具体的条件判断，请查看上面的代码实现：
五、81. 搜寻旋转排序数组 II
假如依照升序排序的数组在事后未知的某个点上进行了旋转。(例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
这道题目在【33. 搜寻旋转排序数组】的根底下来除了”不存在反复元素“这一条件。
回顾 33 题的解法，在寻找下一个搜寻区间时，通过该搜寻区间的头部元素和尾部元素的比拟得出以后搜寻区间是否横跨两个递增序列。一旦没有无反复元素这一条件，那么依据头尾两个元素无奈判断以后搜寻区间是否横跨两个递增序列。
本题要求计算元素的存在性，那么一个元素的反复元素对其存在性是没有任何影响的，所以只有在二分搜寻的过程中，剔除掉头尾部的反复元素即可：
写在最初
算法作为计算机的基础学科，用 JavaScript 刷，一点也不丢人 ε =ε=ε=┏(゜ロ゜;)┛。
本系列文章会别离给出一种算法的 3 种难度的总结篇（简略难度，中等难度以及艰难难度）。在简略难度中，会介绍该算法的基本知识与实现，另外两个难度，着重解说解题的思路。
如果本文对您有所帮忙，能够点赞或者关注来激励博主。
