一、二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
二分查找的前提
有序数组，无重复元素
二分法的写法
1. 左闭右闭，即[ left, right ]
而（左 <= 右）
如果 nums[mid] > trg : 右 = mid-1
def binary_search(nums,target):
left=0
right=len(nums)-1 #定义target在左闭右闭的区间里，[left, right]
while left <= right:
mid= left + (right-left)//2 #防止溢出
if nums[mid] > target:
right = mid-1 #target在左区间
elif nums[mid] < target:
left = mid+1 #target在右区间
else:
return mid
return -12. 左闭右开，即[left, right)
而左<右
如果 nums[mid] > 目标：右=mid
def binary_search(nums, target):
left=0
right=len(nums)
while left < right:
mid = left + (right-left)//2
if nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid+1
else:
return mid
return -1题目与代码
在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题
思路：target在数组里的左右边界存在三种情况
情况一：target在数组范围的左边或右边，如{3，4，5}，target为2或者{3,4,5}，target为6，应该返回[-1,-1]
情况二：target在数组范围内，且数组中不存在target，如{3,5,6}，target为4，应该返回[-1,-1]
情况三：target在 数组范围内，且数组中存在target，如{3,4,5}，target为4，应该返回[1,1]
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def getRightBorder(nums:List[int], target:int) -> int:
left, right = 0, len(nums)-1
rightBoder = -2 # 记录一下rightBorder没有被赋值的情况
while left <= right:
middle = left + (right-left) // 2
if nums[middle] > target:
right = middle - 1
else: # 寻找右边界，nums[middle] == target的时候更新left
left = middle + 1
rightBoder = left
return rightBoder
def getLeftBorder(nums:List[int], target:int) -> int:
left, right = 0, len(nums)-1
leftBoder = -2 # 记录一下leftBorder没有被赋值的情况
while left <= right:
middle = left + (right-left) // 2
if nums[middle] >= target: # 寻找左边界，nums[middle] == target的时候更新right
right = middle - 1
leftBoder = right
else:
left = middle + 1
return leftBoder
leftBoder = getLeftBorder(nums, target)
rightBoder = getRightBorder(nums, target)
# 情况一
if leftBoder == -2 or rightBoder == -2: return [-1, -1]
# 情况三
if rightBoder -leftBoder >1: return [leftBoder + 1, rightBoder - 1]
# 情况二
return [-1, -1]二、移除元素
方法：快慢指针法
快指针：寻找新数组的元素，即不含目标值的元素
慢指针：指向更新新数组下标的位置
**双指针常见于数组、链表和字符串的操作
题目与代码
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
# 快慢指针
fast = 0 # 快指针
slow = 0 # 慢指针
size = len(nums)
while fast < size: # 不加等于是因为，a = size 时，nums[a] 会越界
# slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow三、有序数组的平方
方法：双指针法
∵ 数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间
题目与代码
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
#双指针
result=[0]*len(nums)
l,r,i = 0,len(nums)-1,len(nums)-1
while l <= r:
if nums[r]**2 > nums[l]**2:
result[i]=nums[r]**2
r-=1
else:
result[i]=nums[l]**2
l+=1
i-=1
return result四、长度最小的子数组
方法：滑动窗口
不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果
- 窗口内是什么？
满足和 ≥ s 的长度最小的连续 子数组
- 如何移动窗口的起始位置？
若当前窗口的值 ≥ s，窗口就要向前移动，即缩小窗口的值
- 如何移动窗口的结束位置？
for循环的索引
题目与代码
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
#滑动窗口法
min_len=float('inf') #用于更新最小长度
l,r=0,0
cur_sum=0 #用于累加
while r < len(nums):
cur_sum+=nums[r] #累加
#判断当前值是否超过目标值
while cur_sum >= target:
min_len =min(min_len,r-l+1) #更新长度
#缩小窗口
cur_sum-=nums[l]
l+=1
r+=1
return min_len if min_len != float('inf') else 0五、螺旋矩阵Ⅱ
方法：循环不变量原则
模拟顺时针画矩阵的过程：上行从左到右-右列从上到下-下行从右到左-左列从下到上
每一条边保持相同的左闭右开或者左开右闭的原则
题目与代码
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
# 初始化 n x n 矩阵
matrix = [[0]*n for _ in range(n)]
# 初始化边界和起始值
top, bottom, left, right = 0, n-1, 0, n-1
num = 1
while top <= bottom and left <= right:
# 从左到右填充上边界
for i in range(left, right + 1):
matrix[top][i] = num
num += 1
top += 1
# 从上到下填充右边界
for i in range(top, bottom + 1):
matrix[i][right] = num
num += 1
right -= 1
# 从右到左填充下边界
for i in range(right, left - 1, -1):
matrix[bottom][i] = num
num += 1
bottom -= 1
# 从下到上填充左边界
for i in range(bottom, top - 1, -1):
matrix[i][left] = num
num += 1
left += 1
return matrix六、区间和
方法：前缀和
前缀和的思想是重复利用计算过的子数组之和，从而降低区间查询需要累加计算的次数
前缀和在涉及计算区间和的问题时非常有用
题目与代码
def main():
n=int(input())
cursum=[]
sum=0
for _ in range(n):
num=int(input())
sum+=num
cursum.append(sum)
while True:
try:
a,b=map(int,input().split())
except:
break
if a == 0:
print(cursum[b])
else:
print(cursum[b]-cursum[a-1])
if __name__ == '__main__':
main()七、开发商购买土地
方法：前缀和
本题要求任何两个行（或者列）之间的数值总和，也就是前缀和的思路。分别统计前n行或前n列的和q[n]，a行和b行之间的总和，即q[b]-q[a-1]
题目与代码
n,m=map(int,input().split())
array=[[0]*m for _ in range(n)]
sum=0 #所有元素总和
#存储元素
for i in range(n):
lines=list(map(int,input().split()))
for j in range(len(lines)):
array[i][j]=lines[j]
sum+=lines[j]
#统计横向和
horizon=[0]*n
for i in range(n):
for j in range(m):
horizon[i]+=array[i][j]
#统计纵向和
vertical=[0]*m
for j in range(m):
for k in range(n):
vertical[j]+=array[k][j]
#横向切割
res=float('inf')
horiticalcut=0
for i in range(n):
horiticalcut+=horizon[i]
res=min(res,abs(sum-2*horiticalcut))
#纵向切割
verticalcut=0
for i in range(m):
verticalcut+=vertical[i]
res=min(res,abs(sum-2*verticalcut))
print(res)