數組：基礎概念、存儲特性及力扣實戰應用
在計算機科學與數學的廣袤領域中，數組作為一種極為重要的數據結構，發揮著不可或缺的作用。它就像一個有序的 “數據倉庫”，能高效地存儲和管理大量數據。接下來，讓我們深入了解數組的奧秘。
一、數組的維度與數學表示
（一）向量與一維數組
在數學世界里，向量可表示為\(A = (a_0, a_1, \cdots, a_{n - 1})\)。對應到計算機編程中，這便是一維數組的概念 —— 由n個元素按順序依次排列而成，每個元素\(a_i\)（\(i = 0, 1, \cdots, n - 1\)）都在數組里有著獨一無二的位置。例如，在存儲學生成績時，我們可以創建一個一維數組，數組中的每個元素分別對應一位學生的成績，方便快捷地對成績數據進行處理和管理。
（二）矩陣與二維數組
矩陣的數學表達式為\(A_{m×n}=\begin{bmatrix}a_{00}&a_{01}&\cdots&a_{0,n - 1}\\a_{10}&a_{11}&\cdots&a_{1,n - 1}\\\cdots&\cdots&\cdots&\cdots\\a_{m - 1,0}&a_{m - 1,1}&\cdots&a_{m - 1,n - 1}\end{bmatrix}\)。二維數組可視作由m行n列元素構成的矩陣，其中每個元素\(a_{ij}\)（\(i = 0, 1, \cdots, m - 1\)；\(j = 0, 1, \cdots, n - 1\)）都能通過其所在的行和列唯一確定。在表示棋盤狀態時，二維數組大顯身手，棋盤上每個格子的信息都能精準地存儲在對應的數組元素中。
（三）n 維數組的概念拓展
隨著維度的增加，數組變得更加復雜和靈活。當數組的下標由n個數組成時，就形成了n維數組。訪問這類數組中的元素，需要用到n個索引值。以三維數組為例，它常被用于三維圖形處理、氣象數據存儲（涉及空間的x、y、z坐標以及時間等維度）等場景。依此類推，n維數組能夠借助n個下標確定唯一的元素，為處理復雜的數據關系和多維數據集合提供了強大的支持。
二、數組的存儲特點
（一）內存連續存儲
數組元素在內存中是按順序連續存儲的，這使得計算機在訪問數組元素時能夠快速定位，大大提高了數據的訪問效率。
（二）存儲分配方式
不同編程語言的數組存儲分配方式有所不同。像C、\(C++\)、\(C\#\)等語言，數組按行進行存儲分配；而Fortran語言則是按列進行存儲分配。
（三）數組名的特性
數組名代表該數組在內存中的首地址，并且它是一個常量，在程序運行過程中不能被修改。
三、常用數組的存儲細節
（一）一維數組
對于一維數組\(a[n]\)，其各元素按照下角標依次存放。例如在\(C\#\)中，我們創建一個整型一維數組int[] a = new int[5];，假設每個元素占用的存儲空間為c字節，那么第i個元素的存儲地址\(Loc(a[i]) = Loc(a[0]) + i×c\)?。
（二）二維數組
以二維數組\(a[m,n]\)為例，在\(C\#\)中創建int[,] a = new int[2,3];。若每個元素占用c字節，其元素存儲地址的計算公式為\(Loc(a[i,j]) = Loc(a[0,0]) + (i×n + j)×c\)。這種存儲方式與二維數組的矩陣結構相對應，便于根據行和列的索引快速計算出元素的存儲位置。
（三）三維數組
三維數組的存儲更為復雜，以\(a[m,n,l]\)為例，如在\(C\#\)中創建int[,,] a = new int[2,3,4];。它的存儲規律是第一維下標變化最慢，第三維（最后一維）下標變化最快。每個元素的存儲地址計算公式為\(Loc(a[i,j,k]) = Loc(a[0,0,0]) + (i×n×l + j×l + k)×c\)。這種存儲順序符合人們對三維空間的認知邏輯，方便在處理三維數據時進行高效的訪問和操作。
四、力扣實戰：數組相關算法題解析
（一）最長連續序列（力扣 128 題）
- 題目描述：給定一個未排序的整數數組
nums，要求找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度，并設計實現時間復雜度為\(O(n)\)的算法。 - 示例
- 輸入：
nums = [100,4,200,1,3,2]，輸出：4，解釋：最長數字連續序列是[1, 2, 3, 4]，長度為4。 - 輸入：
nums = [0,3,7,2,5,8,4,6,0,1]，輸出：9。
- 輸入：
- 解題思路與代碼實現
收起
python
from typing import Listclass Solution:def longestConsecutive(self, nums: List[int]) -> int:if not nums: # 增加對空列表的錯誤處理return 0nums_set = set(nums) # 使用集合來提高查找速度length = 0for num in nums_set:if num - 1 in nums_set:continuelst1 = self.findBig(num, nums_set, [num])if len(lst1) > length:length = len(lst1)return lengthdef findBig(self, num, nums_set, lst1):while num + 1 in nums_set:lst1.append(num + 1)num += 1return lst1
在這段代碼中，首先將數組轉換為集合，利用集合查找元素的時間復雜度為\(O(1)\)的特性，提高查找效率。然后遍歷集合中的每個元素，若當前元素的前一個數不在集合中，則以此元素為起點，不斷尋找連續的數字序列，記錄下最長序列的長度并返回。
（二）兩數之和（力扣 1 題）
- 題目描述：給定一個整數數組
nums和一個整數目標值target，需要在數組中找出和為目標值target的兩個整數，并返回它們的數組下標。假設每種輸入只會對應一個答案，且不能使用兩次相同的元素，可按任意順序返回答案。 - 示例
- 輸入：
nums = [2,7,11,15],?target = 9，輸出：[0,1]，解釋：因為nums[0] + nums[1] == 9，所以返回[0, 1]。 - 輸入：
nums = [3,2,4],?target = 6，輸出：[1,2]。
- 輸入：
- 解題思路與代碼實現
收起
python
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:# 創建一個字典來存儲數值與索引的對應關系num_to_index = {}# 遍歷數組一次for i, num in enumerate(nums):# 計算需要的補數complement = target - num# 檢查補數是否在字典中if complement in num_to_index:return [num_to_index[complement], i]# 將當前數值和索引存入字典num_to_index[num] = i# 如果沒有找到符合條件的數值對，拋出異常raise ValueError("沒有找到兩個數，使它們的和等于目標值")
此代碼通過創建一個字典，在遍歷數組的過程中，將每個元素的值和索引存入字典。同時，每次計算當前元素的補數，并檢查補數是否在字典中。若存在，則找到了滿足條件的兩個數，返回它們的索引；若遍歷結束仍未找到，則拋出異常。
數組在數據存儲和算法設計中占據著核心地位。深入理解數組的概念、存儲特性以及在算法題中的應用，能夠為我們在編程之路上打下堅實的基礎，幫助我們更高效地解決各種復雜的問題。希望通過本文的分享，大家能對數組有更全面、更深入的認識，在編程實踐中靈活運用數組知識，提升編程技能。
使用筆記)
