算法与数据结构基础 - 数组(Array)

数组基础

数组是最基础的数据结构，特点是O(1)时间读取任意下标元素，经常应用于排序(Sort)、双指针(Two Pointers)、二分查找(Binary Search)、动态规划(DP)等算法。顺序访问数组、按下标取值是对数组的常见操作。

?

相关LeetCode题：

905.?Sort Array By Parity? 题解

922.?Sort Array By Parity II??题解

977.?Squares of a Sorted Array? 题解

1150.?Check If a Number Is Majority Element in a Sorted Array? 题解

896.?Monotonic Array? 题解

448.?Find All Numbers Disappeared in an Array? 题解

26.?Remove Duplicates from Sorted Array? 题解

88.?Merge Sorted Array? 题解

189.?Rotate Array? 题解

941.?Valid Mountain Array? 题解

31.?Next Permutation? 题解

?

滑动窗口

一前一后指针遍历数组，这种方法叫做滑动窗口(Sliding Window)，也是遍历数组的常用方式。更多关于滑动窗口详见：

算法与数据结构基础 - 滑动窗口(Sliding Window)

?

相关LeetCode题：

1040.?Moving Stones Until Consecutive II??题解

1151.?Minimum Swaps to Group All 1‘s Together??题解

?

Matrix

二维数组即矩阵(Matrix)，也是常见的数据结构，可以用于表示图。

?

相关LeetCode题：

867.?Transpose Matrix??题解

566.?Reshape the Matrix??题解

695.?Max Area of Island? 题解

835.?Image Overlap? 题解

48.?Rotate Image? 题解

54.?Spiral Matrix? 题解

59.?Spiral Matrix II? 题解

?

Prefix sum

Prefix sum是数组、矩阵应用的一个技巧，其有助于降低求解一些子数组问题的时间复杂度。

?

相关LeetCode题：

548.?Split Array with Equal Sum? 题解

209.?Minimum Size Subarray Sum? 题解?

1074.?Number of Submatrices That Sum to Target? 题解?

?

HashTable

数组与HashTable结合使用可以产生一些“火花”、降低一些问题求解的时间复杂度。例如用HashTable为数组元素计数，或用HashTable为数组元素建立反向索引。更多关于HashTable详见：

算法与数据结构基础 - 哈希表(Hash Table)

?

相关LeetCode题：

380.?Insert Delete GetRandom O(1)??题解

560.?Subarray Sum Equals K??题解

954.?Array of Doubled Pairs? 题解