数据结构与算法----学习笔记（2）数组实战部分

LeetCode题型归纳----数组双指针

双指针：指在遍历的过程中不是使用单个指针进行循环访问，而是使用两个指针进行访问，这两个指针可以是同向的，也可以是相反方向的。双指针充分使用了数组有序这一特征，从而在某些情况下能够简化运算

---

双指针算法分类：

相向双指针
同向双指针-快慢指针
同向双指针-滑动窗口
分离双指针

---

相向双指针

在有序数组中，将指向最左侧的索引定义为左指针，最右侧的定义为右指针，从两边向中间遍历
注意：是有序数组，有序数组，有序数组

==============================================================================

均可用相向双指针解题 注意用双指针时数组有序，无序的话先进性排序，如果需要索引的话，要对应回数组的索引 1. 两数之和

解法一：暴力求解
枚举数组中的每一个数x，寻找数组中是否含有target-x
注意，x之前的每一个数都和x组合过，因为是从左往右依次遍历，因此，只需查看x之后的数就行
两重遍历，时间复杂度为O(n2)

解法二：哈希表法
构建一个哈希表，遍历到x值时先查看target-x的值有没有在这个哈希表中，再将x加入，这样就能保证自己和自己不去匹配
时间复杂度为O(n)

解法三：双指针法
注意：有序有序有序，双指针适用条件是有序数组！！！
左右两个指针依次向中间靠拢，每次查边两个指针所指向的数相加和target的大小，如果和大于target则右指针左移，如果和小于target则左指针右移

---

167. 两数之和 II - 输入有序数组

由于是有序数组，使用双指针法

---

15. 三数之和

三数之和，分解为固定一个数+双指针去查找另外两个数

---

16. 最接近的三数之和

三数之和的 *** 作就是，固定一个数，用一个双指针找到另外的两个数，注意，双指针的初始化（即左指针的指向和右指针的指向）在每个固定的数变时也要重新初始化，左指针指向固定数后面的一个数，右指针指向最后的一个数

---

18. 四数之和

通用使用双指针，固定两个数，再用另外两个数去查找合适的数
注意加入剪枝 *** 作

11. 盛最多水的容器

这道题没有用到有序数组
将左右两个指针，使短的一侧向长的一侧移动,每次移动指针的时候需要比较容积的大小

611. 有效三角形的个数

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        count = 0
        for i in range(2,len(nums)):
            left = 0
            right = i-1
            while left<right:
                if nums[left] + nums[right] > nums[i]:
                    count += right-left
                    right -=1
                else :
                    left+=1
        return count

==============================================================================

同向双指针----快慢指针 是指从同一侧开始遍历数组，但是这两个指针的速度（策略）是不一样的

一个快指针fast，一个慢指针slow
一般而言，slow指针所指向的元素及之前都是满足条件的，然后通过fast指针去找到满足条件的元素

26. 删除有序数组中的重复项

注意是原地删除！
返回删除后数组的新长度

27. 移除元素 80. 删除有序数组中的重复项 II 283. 移动零 845. 数组中的最长山脉

思路：先固定山峰的值，分别寻找左半边和右半边的山脉长度

==============================================================================

同向指针----滑动窗口，滑动窗口主要用来处理连续问题 从类型上来说，主要有：

固定窗口大小
窗口大小不固定，求解最大的满足条件的窗口
窗口大小不固定，求解最小的满足条件的窗口

一般而言，快慢指针是慢指针所指向的元素及其之前是满足条件的元素，而快指针是去找到满足条件的元素；滑动窗口是在两个指针之间的元素为满足条件的元素。

239、209 713. 乘积小于K的子数组

解题是：右指针依次右移，计算每个状态下满足的元组数，当不满足条件时，将左指针向右移动

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        left = 0
        product = 1
        count = 0
        for right in range(len(nums)):  # 右指针一个一个的遍历
            product *= nums[right]
            while left<=right and product>=k:
                product /= nums[left]
                left+=1
            count += right-left+1
        return count

分离双指针 输入为两个链表或数组，两个指针分别在两个输入上移动，根据问题的不同，初始位置可能都在头部，或者都在尾部，或一头一尾

总结

1.相向双指针

2.同向双指针----快慢指针
一个slow，一个fast，一般而言从0到slow这个区间中的元素是所需要的元素即满足条件的元素，fast指针是去遍历数组，从而找到满足条件的元素

3.同向双指针----滑动窗口
固定窗口：左右指针一起动
可变窗口：（1）求最大满足条件（2）求最小满足条件
左右指针一般不是一起动，右指针一直去寻找满足条件的元素，达到满足条件后，左指针也向右缩小窗口，看现在的窗口内是否还满足条件（求最小的条件）；也有求最大的条件

4.分离双指针
输入为两个，两个指针分别在两个数组上移动