一、線性表、數(shù)組基礎(chǔ)
很多問題就是在一個數(shù)組中解決的
棧、隊列、堆的底層都是基于數(shù)組，封裝的數(shù)據(jù)結(jié)構(gòu)，后面我們會遇到很靈活的算法問題。本質(zhì)就是在數(shù)組里面做操作。
下面我們來講一個簡單算法，二分查找法：
class Solution(object):
def BinarySearch(self, arr, target):
# [l, r]的區(qū)間采用二分查找法
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]這個區(qū)間，那么進行循環(huán)的時候，控制條件l是可以和r相等的，當target<arr[mid]的時候，說明目標在區(qū)間的左邊，r就應該等于mid-1（因為是開區(qū)間，所以是mid-1）,同理我們可以知道l的取值就是mid+1了。
mid = l+(r-l)//2的寫法是為了防止數(shù)值的溢出，要是寫成(l+r)//2的形式，那么當r和l都非常的大的時候，就可能出現(xiàn)數(shù)值溢出的問題。
時間復雜度：O(logn)
空間復雜度：O(1)
二、一些思路及LeetCode代表題
1、移除元素
LeetCode 283題：移動零
給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:
必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。
盡量減少操作次數(shù)。
思路一：三個for循環(huán)解決問題。用一個格外的數(shù)組來存取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
這種思路的話，多用了一個數(shù)組，帶來了空間復雜度O(n)，下面我們就針對這一點進行一個優(yōu)化。
思路二：采用快慢指針的思想，用慢指針k來指向非零元素，用快指針來遍歷該數(shù)組。循環(huán)完成之后，那么[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循環(huán)就完成了整個操作。[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
到了這里之后，我們還能不能夠進行進一步的優(yōu)化呢？答案是yes。因為很多時候，我們的優(yōu)化都是針對的特殊情況。
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 兩數(shù)之和 II - 輸入有序數(shù)組
給定一個已按照升序排列 的有序數(shù)組，找到兩個數(shù)使得它們相加之和等于目標數(shù)。
函數(shù)應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。
說明:
返回的下標值（index1 和 index2）不是從零開始的。
你可以假設(shè)每個輸入只對應唯一的答案，而且你不可以重復使用相同的元素。
示例:
輸入: numbers = [2, 7, 11, 15], target = 9
輸出: [1,2]
解釋: 2 與 7 之和等于目標數(shù) 9 。因此 index1 = 1, index2 = 2 。
思路一：暴力解法，進行雙層的遍歷，然后時間復雜度是O(n^2)，遍歷i，j，檢測i和j所對應的是不是target。要是一時沒有想法，就能給出結(jié)果，這仍然是一個可行的解決，解決完，提交的話，LeetCode會告訴大家，這是會超時的。數(shù)據(jù)的規(guī)模為10000，運行起來就顯得比較慢了，數(shù)據(jù)規(guī)模要是100000，就不能在我們?nèi)萑缘臅r間內(nèi)完成這個問題。因此我們必須要有更高效的解法。
時間復雜度：O(n^2)
空間復雜度：O(1)
思路二：采用二分搜索法，第一層循環(huán)進行數(shù)組的遍歷，針對每個元素，找剩下部分找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的。下面就是用對撞指針的方式來解決這個問題
思路三：因為我們的數(shù)組是排序過的，然后左邊的小，右邊的大，左邊的開始記為i，右邊的開始記為j，然后看nums[i]和nums[j]的大小，要是他們相等，那么正好i和j就是我們想找的，要是nums[i]+nums[j]<target，那么就說明了nums[i]是小了，那么i就需要向前進，要是nums[i]+nums[j]>target了，就說了nums[j]大了，那么j就需要向前面走了。知道了這個思路之后，我們下面就來進行一個實現(xiàn)：
時間復雜度：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:長度最小的子數(shù)組
給定一個含有 n 個正整數(shù)的數(shù)組和一個正整數(shù) s ，找出該數(shù)組中滿足其和 ≥ s 的長度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。
示例:
輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數(shù)組 [4,3] 是該條件下的長度最小的連續(xù)子數(shù)組。
進階:
如果你已經(jīng)完成了O(n) 時間復雜度的解法, 請嘗試 O(n log n) 時間復雜度的解法。
思路一：第一種思路就是暴力法，采用三次循環(huán)來達到目的，這樣的解決方法的時間復雜度是就是O(n3)，可以將這種方法優(yōu)化到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
持續(xù)更新中...
數(shù)據(jù)結(jié)構(gòu)與算法系列博客：
一、數(shù)據(jù)結(jié)構(gòu)與算法概述
二、數(shù)組及LeetCode典型題目分析
三、鏈表（Linked list）以及LeetCode題
四、棧與隊列（Stack and Queue
五、樹（Trees）
六、遞歸與回溯算法
七、動態(tài)規(guī)劃
八、排序與搜索
九、哈希表
參考資料：
1、https://coding.imooc.com/class/82.html
2、https://leetcode-cn.com/problemset/all/
