一、二分查找
（一）二分查找的思想（二）代码 二、双指针
（一）双指针的思想（二）代码 三、哈希表
（一）哈希表的思想（二）代码 四、滑动窗口算法
（一）滑动窗口的思想（二）代码
一、二分查找 （一）二分查找的思想
二分查找又称折半查找
优点是比较次数少，查找速度快，平均性能好缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 充分利用数组nums已经排好序的特点
我们取数组nums的中间位置(mid)的元素n_1，用n_1与目标数字x进行比较，如果n_1 等于x，那么直接返回n_1的位置mid；如果n_1大于x，则说明x如果在数组中的话，一定是在n_1的左侧；如果n_1小于x，则说明x如果在数组中的话，一定是在n_1的右侧。 （二）代码
class Solution:
def search(self, nums: List[int], target: int) -> int:
# 设置左右指针
left, right = 0, len(nums)-1
while left <= right:
mid = (left+right)//2
if target == nums[mid]:
return mid
elif target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1
二、双指针 （一）双指针的思想
指针的意思是内存空间的地址。可以通过一个数组中每个元素的下标来找出它的值，所以存储这个元素位置的下标值的变量可以看作一个指针。将这个概念来实现python中的指针问题，由于它不是真正意义上的指针，所以我们称为“模拟指针问题”。 （二）代码
给你一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例：
输入：nums = [-4,-1,0,3,10]输出：[0,1,9,16,100]解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
i,j,k = 0,n - 1,n - 1
ans = [-1] * n
while i <= j:
lm = nums[i] ** 2
rm = nums[j] ** 2
if lm > rm:
ans[k] = lm
i += 1
else:
ans[k] = rm
j -= 1
k -= 1
return ans
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。示例：
输入：[1,2,3,4,5]输出：此列表中的结点 3 (序列化形式：[3,4,5])
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
node1,node2 = head,head
while node2.next:
node1 = node1.next
if node2.next.next:
node2 = node2.next.next
else:
node2 = node2.next
return node1
三、哈希表 （一）哈希表的思想
散列表（Hash table，也叫哈希表），是根据关键码值(Key和value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。个人理解：与列表不同的是，哈希表的索引是Key，直接通过Key值访问value，而不同于列表，通过整数[ 0 , ∞ ) 作为索引存储值。python 字典：https://www.runoob.com/python/python-dictionary.html （二）代码
给定一个整数数组nums和一个整数目标值 target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。示例 1：
输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 示例 2：
输入：nums = [3,2,4], target = 6输出：[1,2]
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict_nums = {}
for index in range(0,len(nums)):
value = target - nums[index]
if value in dict_nums:
return [dict_nums[value],index]
dict_nums[nums[index]]=index
return None
四、滑动窗口算法 （一）滑动窗口的思想
利用滑动窗口，从第一个字符开始，逐渐向右查找，当字符出现的类型和频率均满足要求，则找到了一个符合条件的字串。但这个字串可能不是最小字串。接着保持滑动窗口右边界不变，收缩左边界，观察长度减小后字串是否依然满足条件，如果满足，则继续收缩左边界，直到不能收缩为止。如果这个字串长度小于之前找到的字串长度，则更新结果。保持滑动窗口左边界不动（实际上左边界应该往右挪一个），扩张右边界，继续找符合条件的字串。然后通过步骤2，3找到满足条件的最小字串，直到遍历整个字符串S。 （二）代码
给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。示例 1:
输入: s = “abcabcbb”输出: 3解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
# 滑动窗口包含左右两个，因此初始化条件可为left, right = 0, -1
# 由于初始化right为-1，因此当s[right+1]不在数组s（更新的）内，并且长度小于数组的长度，即向右窗口移动，否则向左窗口移动
left,right = 0,-1
max_len = 0
# 终止条件：由于右窗口会先滑到右端，因此终止条件是左窗口在数组长度范围内即可
while left < len(s):
if right+1 < len(s) and s[right+1] not in s[left:right+1]:
right = right + 1
else:
left = left + 1
max_len = max(max_len,right-left+1)
return max_len
