我們知道常用的數據存儲方式有兩種：順序存儲和非順序存儲。順序存儲就是把數據存儲在一塊連續的空間內。數組（array）就是典型的順序存儲，而鍊表就是典型的非順序存儲。
數組通常用於存儲一系列相同類型的數據。當我們在創建數組時，會在內存中劃分出一塊連續的內存用於存儲數據，插入數據時，會將數據按順序存儲在這塊連續的內存中，讀取時通過訪問數組的索引迅速取出。數組名就是一個指針，指向這段內存的起始地址。通過數組的類型，編譯器知道在訪問下一個元素的時候需要在內存中後移多少個字節。由於數組在存儲時是順序存儲的，存儲數據的內存也是連續的，所以數組在讀取數據時比較容易，隨機訪問速度快，但是插入和刪除就比較費勁了。讀取可以直接根據索引，插入和刪除則比較耗時，插一個數據需要移動大量元素，在內存中空出一個元素的空間，然後將要增加的元素放在其中，如果想刪除一個元素，同樣需要移動大量元素去掉被移動的元素。所以如果需求是快速訪問數據，很少或者幾乎不插入和刪除元素，數組是一個不錯的選擇。
最常見的有一維數組和二維數組，稍微複雜一點的是多維數組和動態數組。在c++中，STL提供了Vector，在Java中，Collection集合中提供了ArrayList和Vector,對於Python而言，內置的List就是一個動態指針數組。當列表中沒有空間存儲新的元素時，列表會動態地改變大小以容納新的元素，每次改變大小時，會預留一部分空間以降低改變大小的頻率。
類別
1.無序數組
概念：未經過排序的數組
優點：插入快
缺點：查找慢，刪除慢
2.有序數組
題型總結這類題目通常會給定一個數組和一個值，讓求出這個數組中兩個/三個/K個值的和等於這個給定的值target。leetcode第一題就是two-sum，對於這類題目，首先看題目要求的時間複雜度和空間複雜度是什麼，其次看有沒有限制條件，如要求不能有重複的子數組或者要求按照升序/降序排列等。解法如下：
Leetcode中包含該類型的題目：
這類題目通常會給一個包含多個子數組的數組，然後針對區間是否重合來判斷true or false。
1.按start排序
2.在前一個區間的end和後一個區間的start找交集
例題:252 meeting room[easy]（https://leetcode.com/problems/meeting-rooms/）
題目理解：給定一個數組，包含每個會議的開始時間和結束時間[[s1,e1],[s2,e2],...],判斷一個人能否參加所有的會議。
test case:
Example1:
Input: [[0,30],[5,10],[15,20]]Output: falseExample2:Input: [[7,10],[2,4]]Output: true
Java解法
class Solution{
public boolean canAttendMeetings(Interval[] intervals){
Arrays.sort(intervals,(x,y)->(x.start-y.start);
//i從1開始，因為涉及到判斷前一個數組的end
for (int i =0;i <intervals.length;i++){
if (intervals[i-1].end > intervals[i].start){
return false;
}
}
return true;
Python解法
class Solution(object):
def canAttendMeetings(self, intervals):
"""
:type intervals: List[Interval]
:rtype: bool
"""
intervals.sort(key=lambda x: x.start)
for i in range(1, len(intervals)):
if intervals[i].start < intervals[i-1].end:
return False
return True
Leetcode中包含該類型的題目：
序號題目難度代碼56Merge Intervalsmediumpython、java、c++57Insert Interval hardpython、java、c++252Meeting Roomseasypython、java、c++253Meeting Rooms IImediumpython、java、c++352Data Stream as Disjoint Intervalshardpython、java、c++
3.子數組類題目
這類題目通常會在一個包含多個子數組的數組中，求和/積，最大最小等。形式有很多種，例如求一個數組中和最小的子數組（209題），或者積最小的子數組（238題）
Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
解釋：滿足子數組和=7的最小長度數組是[4,3],所以output=2
解題思路：求的數字要大於等於這個數字target，譬如這個testcase中，[2,3,1,2,4,3]，從前往後相加，前四項相加的和為8.已經大於7了，但是我們的target是7，後面的幾項也都是正整數，繼續往後走，肯定也會大於target7，所以這個時候我們把left指針往右移動一位，那麼就是相當於成為了一個滑動窗口（sliding window），這種方法在String類型的題目出現的更多。
圖1 每一個滑動窗口的變化情況
Java解法
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int res = Integer.MAX_VALUE;//因為是求min，所以設定是Max_VALUE，然後最後的res比較就行，注意res不是0
int left = 0,sum = 0;
for (int i = 0;i<nums.length;i++){
sum += nums[i];//每遍歷一次，就把前i次數字相加求和
while (left <= i && sum >=s){
res = Math.min(res, i-left+1);
sum -= nums[left++];
}
}
return res == Integer.MAX_VALUE? 0:res;
Python解法
class Solution:
def minSubArrayLen(self, s, nums):
total = left = 0
result = len(nums) + 1
for right, n in enumerate(nums):
total += n
while total >= s:
result = min(result, right - left + 1)
total -= nums[left]
left += 1
return result if result <= len(nums) else 0
Leetcode中包含該類型的題目：
序號
題目難度代碼78Subsetsmediumpython、java、c++90Subsets IImediumpython、java、c++53Maximum Subarrayeasypython、java、c++325Maximum Size Subarray Sum Equals kmediumpython、java、c++209Minimum Size Subarray Summediumpython、java、c++238Product of Array Except Selfmediumpython、java、c++152Maximum Product Subarraymediumpython、java、c++239Sliding Window Maximumhardpython、java、c++295Find Median from Data Streamhardpython、java、c++228Summary Rangesmediumpython、java、c++163Missing Rangesmediumpython、java、c++
以上的三種都屬於一維度數組的常見題型，除此之外還有二維數組、N維數組和綜合題的題型總結，可以在leetcode-book（https://github.com/huxiaoman7/leetcodebook）看後續總結。如何按tag刷題
打開官網www.leetcode.com，選擇problems，右下有tags標籤，即可選擇按照不同題型刷題。我總結的題型裡包含了該tag下面的題和補充的一些題，可以以我github的leetcode-book上的題型順序來刷。
後續題型總結和leetcode題目list會在github上更新，本人能力有限，歡迎提留言和提issue討論~