算法|一周刷爆LeetCode，关于数据结构与算法，看这篇刷题笔记就够了( 二 ) 牛顿

双指针算法：数组完成排序后，我们可以放置两个指针 i 和 j ，其中 i 是慢指针，而 j 是快指针。只要nums[i
=nums[j
，我们就增加 j 以跳过重复项。
当遇到 nums[j
！= nums[i
时，跳过重复项的运行已经结束，必须把nums[j
）的值复制到 nums[i +1
。然后递增 i ，接着将再次重复相同的过程，直到 j 到达数组的末尾为止。

x的平方根在不使用 sqrt(x) 函数的情况下，得到 x的平方根的整数部分
解法一：二分查找x的平方根肯定在0到x之间，使用二分查找定位该数字，该数字的平方一定是最接近x的， m平方值如果大于x、则往左边找，如果小于等于x则往右边找
找到0和X的最中间的数m ，
如果m * m > x ，则m取x/2到x的中间数字，直到m * m < x ， m则为平方根的整数部分如果m * m <= x ，则取0到x/2的中间值，知道两边的界限重合，找到最大的整数，则为x平方根的整数部分
时间复杂度：O(logN)

解法二：牛顿迭代假设平方根是 i，则 i 和 x/i 必然都是x的因子，而 x/i 必然等于 i，推导出 i + x / i = 2 * i ，得出 i = (i +x / i) / 2
由此得出解法， i 可以任选一个值，只要上述公式成立， i 必然就是x的平方根，如果不成立，(i + x / i) /2得出的值进行递归，直至得出正确解

三个数的最大乘积一个整型数组 nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。
乘积不会越界
如果数组中全是非负数，则排序后最大的三个数相乘即为最大乘积；如果全是非正数，则最大的三个数相乘同样也为最大乘积。
如果数组中有正数有负数，则最大乘积既可能是三个最大正数的乘积，也可能是两个最小负数（即绝对值最大）与最大正数的乘积。
分别求出三个最大正数的乘积，以及两个最小负数与最大正数的乘积，二者之间的最大值即为所求答案。
解法一：排序
解法二：线性扫描

两数之和给定一个升序排列的整数数组 numbers，从数组中找出两个数满足相加之和等于目标数 target。
假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。
返回两数的下标值，以数组形式返回
暴力解法

时间复杂度：O(N的平方)
空间复杂度：O(1)
哈希表：将数组的值作为key存入map ， target - num作为key

时间复杂度：O(N)
空间复杂度：O(N)
解法一：二分查找先固定一个值(从下标0开始) ，再用二分查找查另外一个值，找不到则固定值向右移动，继续二分查找

时间复杂度：O(N * logN)
空间复杂度：O(1)
解法二：双指针左指针指向数组head ，右指针指向数组tail ， head+tail > target 则tail 左移，否则head右移

时间复杂度：O(N)
空间复杂度：O(1)
斐波那契数列求取斐波那契数列第N位的值。
斐波那契数列：每一位的值等于他前两位数字之和。前两位固定 0 ， 112358 。。。。
解法一：暴力递归

解法二：去重递归递归得出具体数值之后、存储到一个集合(下标与数列下标一致) ，后面递归之前先到该集合查询一次，如果查到则无需递归、直接取值。查不到再进行递归计算

解法三：双指针迭代基于去重递归优化，集合没有必要保存每一个下标值，只需保存前两位即可，向后遍历，得出N的值

环形链表给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达该节点，则链表中存在环如果链表中存在环，则返回 true。否则，返回 false。