前言
今天是算法训练营开营第一天，希望能在后面的日子里完整刷完一次题单。然而，刷完一次题单的flag从 2024 上半年就已立下，每次都因为各种各样的原因导致没能完成计划，不说行百里者半九十，每次重新拾起来都从头开始，磨了一年半了进度依旧少得可怜。
这次，我想走到最后。
704.二分查找
题目链接：704.二分查找
思路
首先说下思路，这道题目已经交手过很多次了，思路主要是用暴力和二分法
暴力的思路比较简单，遍历该数组如果找到目标值就返回下标这里不过多赘述。
二分法是这道题的主题，二分法时间复杂度较低，二分法的写法主要有两种：一种是左闭右闭区间另一种是左闭右开区间，这道题我个人比较倾向前者，这两者的区别主要体现在写循环条件和判断middle更新逻辑时。
如果使用左闭右闭，在判断循环条件时可以存在left == right 的情况，而后者不行；在判断middle 更新逻辑时，后者将right值直接更新为middle，因为这种情况下查询区间在[left, middle)中，不会比较nums[middle] ，所以没必要减 1。
暴力写法
class Solution:
def search(self, nums: List[int], target: int) -> int:
for i in range(0,len(nums)):
if nums[i] == target:
return i
return -1
时间复杂度为O(n)
空间复杂度为O(1)
二分法写法（仅记录左闭右闭）
class Solution:
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
if nums[mid] > target:
right = mid - 1
if nums[mid] == target:
return mid
return -1时间复杂度为O(log n)
空间复杂度为O(1)
附加题｜35.搜索插入位置
题目链接：35.搜索插入位置
二分法写法
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
return mid
return right + 1思路与 704 题大致一致，只是新增了如果最终没找到目标值的插入位置判断逻辑
时间复杂度为O(log n)
空间复杂度为O(1)
附加题｜34.在排序数组中查找元素的第一个和最后一个位置
双指针写法
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left = 0
right = len(nums) - 1
lb = -2
rb = -2
while left < len(nums):
if nums[left] == target:
lb = left
break
left += 1
while right >= 0:
if nums[right] == target:
rb = right
break
right -= 1
if lb != -2 and rb != -2:
return [lb, rb]
if lb != -2 and rb == -2:
return [lb, lb]
if lb == -2 and rb != -2:
return [rb, rb]
return [-1,-1]这道题和之前稍有不同，我的答题思路是在两端定义指针，两段指针分别向中间内收，如果找到 target 值就进行记录到边界值作为结果，同时结束循环，最终将两个边界输出。二分法的总体思路与之相同，只是在寻找边界值的过程中产生区别，但由于这道题数组里的元素是顺序排列的所以用双指针内收我个人觉得相对好理解一些。
时间复杂度为O(n)
空间复杂度为O(1)
27.移除元素
题目链接：27. 移除元素
思路
这道题的大体思路是暴力和双指针法，这两个解法思路上存在共同点，暴力做法是遍历整个数组，如果找到目标值，则将后面所有元素前移一位，同时将整个数组的大小减一，这样就不会导致数组大小在元素删除后异常；双指针法是定义快慢指针，如果快指针所指非目标值，则将慢指针处数值更新为快指针处数值，同时慢指针后移一位。
暴力写法
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i = 0
size = len(nums)
while i < size:
if nums[i] == val:
j = i + 1
while j < size:
nums[j - 1] = nums[j]
j += 1
i -= 1
size -= 1
i += 1
return size时间复杂度为O(n ^ 2)
空间复杂度为O(1)
双指针写法
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow = 0
fast = 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow时间复杂度为O(n)
空间复杂度为O(1)
977.有序数组的平方
题目链接：977. 有序数组的平方
思路
这道题的思路主要是暴力和双指针法，暴力比较无聊所以这里不继续展示，我们主要使用的是双指针法，这道题里最关键的考量点是数组内原本的负数在平方后会放在什么位置，因此我们主要工作是将负数平方与正数平方比较逻辑理清，那么在这道题里我们又新建了一个长度相等的数组来存放结果，而我们的结果存放方式也是从最大往最小开始放，在每次存放前比较左指针与右指针所指值平方大小，根据结果存放数值并调整指针位置。
双指针写法
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
left = 0
right = len(nums) - 1
k = len(nums) - 1
result = [float('inf')] * len(nums)
while left <= right:
if nums[left] * nums[left] < nums[right] * nums[right]:
result[k] = nums[right] * nums[right]
right -=1
else:
result[k] = nums[left] * nums[left]
left += 1
k -= 1
return result时间复杂度为O(n)
空间复杂度为O(n)
总结
在算法训练营第一天的题目里，我们主要学习和练习了暴力、二分法和双指针法三种解题思路，其中二分法需要注意左闭右闭和左闭右开两种方式的书写情况有所区别。
