數(shù)組(Array)

數(shù)組（Array）應(yīng)該是最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)之一，它由相同類型的元素組成的集合，并按照一定的順序存儲在內(nèi)存中。每個元素都有一個唯一的索引，可以用于訪問該元素。

	// java 數(shù)組示例
	int[] numbers1 = {2,0,2,3,9,23};
	// 或者
	int[] numbers2 = new int[6];

基本概念

數(shù)組基本概念 —— 數(shù)組索引、數(shù)組元素、數(shù)組長度

• 數(shù)組索引（Index）： 數(shù)組中的每個元素都有一個唯一的整數(shù)索引，從0開始計數(shù)。索引用于訪問數(shù)組中的元素。
• 數(shù)組元素（Element）： 數(shù)組中的元素必須是相同類型的數(shù)據(jù)，可以是整數(shù)、浮點數(shù)、字符、對象等。
• 數(shù)組長度（Length）： 數(shù)組的長度是指數(shù)組中包含的元素數(shù)量。

其具備一些性質(zhì)：

• 連續(xù)存儲（Contiguous Memory）： 數(shù)組中的元素在內(nèi)存中是連續(xù)存儲的，這意味著通過索引可以直接計算出元素的地址。
• 隨機訪問時間（Constant Time Access）： 由于元素的連續(xù)存儲和索引的存在，通過索引訪問數(shù)組中的某個元素通常只需要常數(shù)時間O(1)。（ PS: 什么叫隨機訪問？ 是計算機領(lǐng)域的一個重要概念，指的是能夠以大致相等的時間訪問存儲介質(zhì)中的任何數(shù)據(jù)元素，而不受其物理存儲位置順序的限制。通俗點說，隨便獲取任意一個元素。）

基本應(yīng)用（Basic）

數(shù)組的結(jié)構(gòu)本身比較簡單，在解決常見面試算法問題中靈活應(yīng)用數(shù)組索引來訪問數(shù)據(jù)是關(guān)鍵。

Leetcode 26. 刪除有序數(shù)組中的重復(fù)項【簡單】

給你一個 非嚴(yán)格遞增排列 的數(shù)組 nums ，請你 原地 刪除重復(fù)出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 ，返回刪除后數(shù)組的新長度。元素的 相對順序 應(yīng)該保持 一致 。然后返回 nums 中唯一元素的個數(shù)。

LeetCode 674. 最長連續(xù)遞增序列【簡單】

給定一個未經(jīng)排序的整數(shù)數(shù)組，找到最長且 連續(xù)遞增的子序列，并返回該序列的長度。

連續(xù)遞增的子序列 可以由兩個下標(biāo) l 和 r（l < r）確定，如果對于每個 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續(xù)遞增子序列。

雙指針（Two Pointers）

一些資料上也有說雙指針?biāo)惴ǎP者看來更傾向于是一種技巧，定義的兩個索引指針 通過操作兩個索引指針來獲取問題答案。（PS：為什么這里叫指針？指針更多的是C語言中的概念，最早C語言解決算法問題比較多。）

根據(jù)指針移動 或者 所指位置不同，也有不少其他種分類的說法比如：對撞指針、快慢指針、分離指針等等；但其技巧本質(zhì)都是在于操作兩個指針?biāo)饕?，大可不必?yán)格定義這些名稱，需要的是抓住重點操作兩個指針。

LeetCode 167. 兩數(shù)之和 II - 輸入有序數(shù)組【中等】

給你一個下標(biāo)從 1 開始的整數(shù)數(shù)組 numbers ，該數(shù)組已按 非遞減順序排列 ，請你從數(shù)組中找出滿足相加之和等于目標(biāo)數(shù) target 的兩個數(shù)。如果設(shè)這兩個數(shù)分別是 numbers[index1] 和 numbers[index2] ，則 1 <= index1 < index2 <= numbers.length 。

以長度為 2 的整數(shù)數(shù)組 [index1, index2] 的形式返回這兩個整數(shù)的下標(biāo) index1 和 index2。
你可以假設(shè)每個輸入 只對應(yīng)唯一的答案 ，而且你 不可以 重復(fù)使用相同的元素。

LeetCode 15. 三數(shù)之和【中等】

給你一個整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請你返回所有和為 0 且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

前綴和（Prefix Sum）

對于一些算法問題直接求解的思路可能計算量比較大，可以思考利用預(yù)處理一組特定的中間數(shù)據(jù)來進求解。類比就如同初中解一些幾何題通過幾條輔助線的解法，如果回顧學(xué)習(xí)輔助線的畫法，往往先了解常見的畫法；對于算法，前綴和就是“常見的輔助線畫法”。

針對一些算法問題需要快速計算數(shù)組某個連續(xù)區(qū)間的數(shù)值和時，先計算前綴和數(shù)組會是一個很好的策略。相關(guān)推導(dǎo)如下：

LeetCode 1343. 大小為 K 且平均值大于等于閾值的子數(shù)組數(shù)目【中等】

給你一個整數(shù)數(shù)組 arr 和兩個整數(shù) k 和 threshold 。
請你返回長度為 k 且平均值大于等于 threshold 的子數(shù)組數(shù)目。

示例 1：
輸入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
輸出：3
解釋：子數(shù)組 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分別為 4，5 和 6 。其他長度為 3 的子數(shù)組的平均值都小于 4 （threshold 的值)。

文章來源地址http://www.zghlxwxcb.cn/news/detail-710837.html

總結(jié)下

• 介紹了數(shù)組的基本結(jié)構(gòu)，三個基本概念： 數(shù)組索引、數(shù)組元素、數(shù)組長度；
• 數(shù)組類基礎(chǔ)題，關(guān)鍵在于靈活的三個基本概念；
• 利用操作兩個數(shù)組索引的編程技巧來解決問題（雙指針）；
• 解決算法問題，求解C，可以先 A->B->C來進行思考，前綴和就是典型一種示例。

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法 | 數(shù)組(Array)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！