一、线性表、数组基础
很多问题就是在一个数组中解决的
栈、队列、堆的底层都是基于数组，封装的数据结构，后面我们会遇到很灵活的算法问题。本质就是在数组里面做操作。
下面我们来讲一个简单算法，二分查找法：
class Solution(object):
def BinarySearch(self, arr, target):
# [l, r]的区间采用二分查找法
l, r = 0, len(arr) -1
while l <= r:
mid = l+(r-l)//2
if target == arr[mid]:
return mid
elif target > arr[mid]:
l = mid +1
else:
r = mid -1
return -1
由于我们选用了[l, r]这个区间，那么进行循环的时候，控制条件l是可以和r相等的，当target<arr[mid]的时候，说明目标在区间的左边，r就应该等于mid-1（因为是开区间，所以是mid-1）,同理我们可以知道l的取值就是mid+1了。
mid = l+(r-l)//2的写法是为了防止数值的溢出，要是写成(l+r)//2的形式，那么当r和l都非常的大的时候，就可能出现数值溢出的问题。
时间复杂度：O(logn)
空间复杂度：O(1)
二、一些思路及LeetCode代表题
1、移除元素
LeetCode 283题：移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
思路一：三个for循环解决问题。用一个格外的数组来存取nums中的非0元素，然后一一赋值到nums中，nums剩下的位置全部赋予0就行了。
时间复杂度：O(n)
空间复杂度：O(n)
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
nonZeros= []
for i in nums:
if i:
nonZeros.append(i)
for i in range(len(nonZeros)):
nums[i] = nonZeros[i]
for i in range(len(nonZeros),len(nums)):
nums[i]=0
这种思路的话，多用了一个数组，带来了空间复杂度O(n)，下面我们就针对这一点进行一个优化。
思路二：采用快慢指针的思想，用慢指针k来指向非零元素，用快指针来遍历该数组。循环完成之后，那么[0,...,k)中都是非0元素。我们后面需要做的就是将后面的元素赋值为0，这样就完成了这个思路
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
k = 0
for index,item in enumerate(nums):
if item:
nums[k]=item
k+=1
for i in range(k, len(nums)):
nums[i]=0
想到这里来了之后，我们就会思考，还能不能将这个算法变得更好呢？答案是yes。
思路三：我们还是采用了快慢指针的操作，然后将非0元素和0元素进行一个互换，这样的话，就一个for循环就完成了整个操作。[0,...,k)中都是非0元素, [k,...,len(nums)]就是0元素了。
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
k = 0
for index, item in enumerate(nums):
if item:
nums[k], nums[index] = nums[index],nums[k]
k+=1
到了这里之后，我们还能不能够进行进一步的优化呢？答案是yes。因为很多时候，我们的优化都是针对的特殊情况。
class Solution:
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: void Do not return anything, modify nums in-place instead.
"""
k = 0
for index, item in enumerate(nums):
if item:
if index!=k:
nums[k], nums[index] = nums[index],nums[k]
k+=1
else:
k+=1
下面还有一些类似于改思想的题目：
LeetCode 26, 27, 80
小伙伴们可以自己去尝试一下
2、对撞指针法
LeetCode 167 两数之和 II - 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
思路一：暴力解法，进行双层的遍历，然后时间复杂度是O(n^2)，遍历i，j，检测i和j所对应的是不是target。要是一时没有想法，就能给出结果，这仍然是一个可行的解决，解决完，提交的话，LeetCode会告诉大家，这是会超时的。数据的规模为10000，运行起来就显得比较慢了，数据规模要是100000，就不能在我们容仍的时间内完成这个问题。因此我们必须要有更高效的解法。
时间复杂度：O(n^2)
空间复杂度：O(1)
思路二：采用二分搜索法，第一层循环进行数组的遍历，针对每个元素，找剩下部分找target-element是不是存在，存在返回就行了。然后试了一下，是accept的。因为前面讲了二分查找法，大家思考一下，这个方法还是挺简单的。
时间复杂度：O(nlogn)
空间复杂度：O(1)
class Solution:
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
n = len(numbers)
for index, item in enumerate(numbers):
if index<n-1:
l, r = index+1, n-1
while l<=r:
mid = l+(r-l)//2
if numbers[mid]==target-item:
return [index+1, mid+1]
elif numbers[mid]>target-item:
r=mid-1
else:
l=mid+1
return None
到这里之后，我们想一想还有没有更加高效的方法来解决这个问题呢？答案是yes的。下面就是用对撞指针的方式来解决这个问题
思路三：因为我们的数组是排序过的，然后左边的小，右边的大，左边的开始记为i，右边的开始记为j，然后看nums[i]和nums[j]的大小，要是他们相等，那么正好i和j就是我们想找的，要是nums[i]+nums[j]<target，那么就说明了nums[i]是小了，那么i就需要向前进，要是nums[i]+nums[j]>target了，就说了nums[j]大了，那么j就需要向前面走了。知道了这个思路之后，我们下面就来进行一个实现：
时间复杂度：O(n)
空间复杂度：O(1)
class Solution(object):
def twoSum(self, numbers, target):
"""
:type numbers: List[int]
:type target: int
:rtype: List[int]
"""
l, r = 0, len(numbers)-1
while l<r:
if numbers[l] + numbers[r]==target:
return [l+1, r+1]
elif numbers[l] + numbers[r]<target:
l+=1
else:
r-=1
采用了对撞指针的题目还有：
Leetcode 11, 125, 344, 345
大家可以去尝试一下这些简单、中等的题目哈
3、滑动窗口法
Leetcode 209:长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
思路一：第一种思路就是暴力法，采用三次循环来达到目的，这样的解决方法的时间复杂度是就是O(n3)，可以将这种方法优化到O(n2)去。
思路二：采用滑动窗口法，
时间复杂度：O(n)
空间复杂度：O(1)
class Solution:
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
sum = 0
l,r=0,-1
res=len(nums)+1
while l<len(nums):
if r+1<len(nums) and sum<s:
r+=1
sum+=nums[r]
else:
sum-=nums[l]
l+=1
if sum>=s:
res = min(res, r-l+1)
if res==len(nums)+1:
return 0;
return res
欢迎各位小伙伴批评指正哈。
类似的题目如下：
Leetcode 3, 76, 438
持续更新中...
数据结构与算法系列博客：
一、数据结构与算法概述
二、数组及LeetCode典型题目分析
三、链表（Linked list）以及LeetCode题
四、栈与队列（Stack and Queue
五、树（Trees）
六、递归与回溯算法
七、动态规划
八、排序与搜索
九、哈希表
参考资料：
1、https://coding.imooc.com/class/82.html
2、https://leetcode-cn.com/problemset/all/
网友评论