Javascript 數(shù)組

對(duì)象允許存儲(chǔ)鍵值集合，這很好。

但很多時(shí)候我們發(fā)現(xiàn)還需要 有序集合，里面的元素都是按順序排列的。例如，我們可能需要存儲(chǔ)一些列表，比如用戶、商品以及 HTML 元素等。

使用對(duì)象就不是很方便了，因?yàn)閷?duì)象不能提供能夠管理元素順序的方法。我們不能在已有的元素“之間”插入一個(gè)新的屬性。這種場(chǎng)景下對(duì)象就不太適用了。

這時(shí)一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)數(shù)組（Array）就派上用場(chǎng)了，它能存儲(chǔ)有序的集合。

聲明

創(chuàng)建一個(gè)空數(shù)組有兩種語法：

let arr = new Array();
let arr = [];

絕大多數(shù)情況下使用的都是第二種語法。我們可以在方括號(hào)中添加初始元素：

let fruits = ["Apple", "Orange", "Plum"];

數(shù)組元素從 0 開始編號(hào)。

我們可以通過方括號(hào)中的數(shù)字獲取元素：

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits[0] ); // Apple
alert( fruits[1] ); // Orange
alert( fruits[2] ); // Plum

可以替換元素：

fruits[2] = 'Pear'; // 現(xiàn)在變成了 ["Apple", "Orange", "Pear"]

……或者向數(shù)組新加一個(gè)元素：

fruits[3] = 'Lemon'; // 現(xiàn)在變成 ["Apple", "Orange", "Pear", "Lemon"]

length 屬性的值是數(shù)組中元素的總個(gè)數(shù)：

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits.length ); // 3

也可以用 ?alert ?來顯示整個(gè)數(shù)組。

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits ); // Apple,Orange,Plumlet fruits = ["Apple", "Orange", "Plum"];

alert( fruits ); // Apple,Orange,Plum

數(shù)組可以存儲(chǔ)任何類型的元素。

例如：

// 混合值
let arr = [ 'Apple', { name: 'John' }, true, function() { alert('hello'); } ];

// 獲取索引為 1 的對(duì)象然后顯示它的 name
alert( arr[1].name ); // John

// 獲取索引為 3 的函數(shù)并執(zhí)行
arr[3](); // hello

以逗號(hào)結(jié)尾

數(shù)組就像對(duì)象一樣，可以以逗號(hào)結(jié)尾：

let fruits = [
  "Apple",
  "Orange",
  "Plum",
];

因?yàn)槊恳恍卸际窍嗨频?，所以這種以“逗號(hào)結(jié)尾”的方式使得插入/移除項(xiàng)變得更加簡(jiǎn)單。

使用 “at” 獲取最后一個(gè)元素

最近新增的特性

這是一個(gè)最近添加到 JavaScript 的特性。 舊式瀏覽器可能需要 polyfills.

假設(shè)我們想要數(shù)組的最后一個(gè)元素。

一些編程語言允許我們使用負(fù)數(shù)索引來實(shí)現(xiàn)這一點(diǎn)，例如 fruits[-1]。

但在 JavaScript 中這行不通。結(jié)果將是 undefined，因?yàn)榉嚼ㄌ?hào)中的索引是被按照其字面意思處理的。

我們可以顯式地計(jì)算最后一個(gè)元素的索引，然后訪問它：fruits[fruits.length - 1]。

let fruits = ["Apple", "Orange", "Plum"];

alert( fruits[fruits.length-1] ); // Plum

有點(diǎn)麻煩，不是嗎？我們需要寫兩次變量名。

幸運(yùn)的是，這里有一個(gè)更簡(jiǎn)短的語法 fruits.at(-1)：

let fruits = ["Apple", "Orange", "Plum"];

// 與 fruits[fruits.length-1] 相同
alert( fruits.at(-1) ); // Plum

換句話說，arr.at(i)：

• 如果 ?i >= 0?，則與 ?arr[i]? 完全相同。
• 對(duì)于 ?i? 為負(fù)數(shù)的情況，它則從數(shù)組的尾部向前數(shù)。

pop/push, shift/unshift 方法

隊(duì)列（queue）是最常見的使用數(shù)組的方法之一。在計(jì)算機(jī)科學(xué)中，這表示支持兩個(gè)操作的一個(gè)有序元素的集合：

• ?push ?在末端添加一個(gè)元素.
• ?shift ?取出隊(duì)列首端的一個(gè)元素，整個(gè)隊(duì)列往前移，這樣原先排第二的元素現(xiàn)在排在了第一。

這兩種操作數(shù)組都支持。

隊(duì)列的應(yīng)用在實(shí)踐中經(jīng)常會(huì)碰到。例如需要在屏幕上顯示消息隊(duì)列。

數(shù)組還有另一個(gè)用例，就是數(shù)據(jù)結(jié)構(gòu) 棧。

它支持兩種操作：

• ?push ?在末端添加一個(gè)元素.
• ?pop ?從末端取出一個(gè)元素.

所以新元素的添加和取出都是從“末端”開始的。

棧通常被被形容成一疊卡片：要么在最上面添加卡片，要么從最上面拿走卡片：

對(duì)于棧來說，最后放進(jìn)去的內(nèi)容是最先接收的，也叫做 LIFO（Last-In-First-Out），即后進(jìn)先出法則。而與隊(duì)列相對(duì)應(yīng)的叫做 FIFO（First-In-First-Out），即先進(jìn)先出。

JavaScript 中的數(shù)組既可以用作隊(duì)列，也可以用作棧。它們?cè)试S你從首端/末端來添加/刪除元素。

這在計(jì)算機(jī)科學(xué)中，允許這樣的操作的數(shù)據(jù)結(jié)構(gòu)被稱為 雙端隊(duì)列（deque）。

作用于數(shù)組末端的方法：

?pop?

取出并返回?cái)?shù)組的最后一個(gè)元素：

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.pop() ); // 移除 "Pear" 然后 alert 顯示出來

alert( fruits ); // Apple, Orange

fruits.pop() 和 fruits.at(-1) 都返回?cái)?shù)組的最后一個(gè)元素，但 fruits.pop() 同時(shí)也刪除了數(shù)組的最后一個(gè)元素，進(jìn)而修改了原數(shù)組。

?push
?

在數(shù)組末端添加元素：

let fruits = ["Apple", "Orange"];

fruits.push("Pear");

alert( fruits ); // Apple, Orange, Pear

調(diào)用 fruits.push(...) 與 fruits[fruits.length] = ... 是一樣的。

作用于數(shù)組首端的方法：

?shift?

取出數(shù)組的第一個(gè)元素并返回它：

let fruits = ["Apple", "Orange", "Pear"];

alert( fruits.shift() ); // 移除 Apple 然后 alert 顯示出來

alert( fruits ); // Orange, Pear

?unshift?

在數(shù)組的首端添加元素：

let fruits = ["Orange", "Pear"];

fruits.unshift('Apple');

alert( fruits ); // Apple, Orange, Pear

push 和 unshift 方法都可以一次添加多個(gè)元素：

let fruits = ["Apple"];

fruits.push("Orange", "Peach");
fruits.unshift("Pineapple", "Lemon");

// ["Pineapple", "Lemon", "Apple", "Orange", "Peach"]
alert( fruits );

內(nèi)部

數(shù)組是一種特殊的對(duì)象。使用方括號(hào)來訪問屬性 arr[0] 實(shí)際上是來自于對(duì)象的語法。它其實(shí)與 obj[key] 相同，其中 arr 是對(duì)象，而數(shù)字用作鍵（key）。

它們擴(kuò)展了對(duì)象，提供了特殊的方法來處理有序的數(shù)據(jù)集合以及 length 屬性。但從本質(zhì)上講，它仍然是一個(gè)對(duì)象。

記住，在 JavaScript 中只有 8 種基本的數(shù)據(jù)類型（詳見 數(shù)據(jù)類型 一章）。數(shù)組是一個(gè)對(duì)象，因此其行為也像一個(gè)對(duì)象。

例如，它是通過引用來復(fù)制的：

let fruits = ["Banana"]

let arr = fruits; // 通過引用復(fù)制 (兩個(gè)變量引用的是相同的數(shù)組)

alert( arr === fruits ); // true

arr.push("Pear"); // 通過引用修改數(shù)組

alert( fruits ); // Banana, Pear — 現(xiàn)在有 2 項(xiàng)了

……但是數(shù)組真正特殊的是它們的內(nèi)部實(shí)現(xiàn)。JavaScript 引擎嘗試把這些元素一個(gè)接一個(gè)地存儲(chǔ)在連續(xù)的內(nèi)存區(qū)域，就像本章的插圖顯示的一樣，而且還有一些其它的優(yōu)化，以使數(shù)組運(yùn)行得非常快。

但是，如果我們不像“有序集合”那樣使用數(shù)組，而是像常規(guī)對(duì)象那樣使用數(shù)組，這些就都不生效了。

例如，從技術(shù)上講，我們可以這樣做:

let fruits = []; // 創(chuàng)建一個(gè)數(shù)組

fruits[99999] = 5; // 分配索引遠(yuǎn)大于數(shù)組長(zhǎng)度的屬性

fruits.age = 25; // 創(chuàng)建一個(gè)具有任意名稱的屬性

這是可以的，因?yàn)閿?shù)組是基于對(duì)象的。我們可以給它們添加任何屬性。

但是 Javascript 引擎會(huì)發(fā)現(xiàn)，我們?cè)谙袷褂贸Ｒ?guī)對(duì)象一樣使用數(shù)組，那么針對(duì)數(shù)組的優(yōu)化就不再適用了，然后對(duì)應(yīng)的優(yōu)化就會(huì)被關(guān)閉，這些優(yōu)化所帶來的優(yōu)勢(shì)也就蕩然無存了。

數(shù)組誤用的幾種方式:

• 添加一個(gè)非數(shù)字的屬性，比如 ?arr.test = 5?。
• 制造空洞，比如：添加 ?arr[0]?，然后添加 ?arr[1000]? (它們中間什么都沒有)。
• 以倒序填充數(shù)組，比如 ?arr[1000]?，?arr[999]? 等等。

請(qǐng)將數(shù)組視為作用于 有序數(shù)據(jù) 的特殊結(jié)構(gòu)。它們?yōu)榇颂峁┝颂厥獾姆椒?。?shù)組在 JavaScript 引擎內(nèi)部是經(jīng)過特殊調(diào)整的，使得更好地作用于連續(xù)的有序數(shù)據(jù)，所以請(qǐng)以正確的方式使用數(shù)組。如果你需要任意鍵值，那很有可能實(shí)際上你需要的是常規(guī)對(duì)象 {}。

性能

push/pop 方法運(yùn)行的比較快，而 shift/unshift 比較慢。

為什么作用于數(shù)組的末端會(huì)比首端快呢？讓我們看看在執(zhí)行期間都發(fā)生了什么：

fruits.shift(); // 從首端取出一個(gè)元素

只獲取并移除索引 0 對(duì)應(yīng)的元素是不夠的。其它元素也需要被重新編號(hào)。

shift 操作必須做三件事：

1. 移除索引為 ?0? 的元素。
2. 把所有的元素向左移動(dòng)，把索引 ?1? 改成 ?0?，?2? 改成 ?1? 以此類推，對(duì)其重新編號(hào)。
3. 更新 ?length ?屬性。

數(shù)組里的元素越多，移動(dòng)它們就要花越多的時(shí)間，也就意味著越多的內(nèi)存操作。

unshift 也是一樣：為了在數(shù)組的首端添加元素，我們首先需要將現(xiàn)有的元素向右移動(dòng)，增加它們的索引值。

那 push/pop 是什么樣的呢？它們不需要移動(dòng)任何東西。如果從末端移除一個(gè)元素，pop 方法只需要清理索引值并縮短 length 就可以了。

pop 操作的行為：

fruits.pop(); // 從末端取走一個(gè)元素

pop 方法不需要移動(dòng)任何東西，因?yàn)槠渌囟急Ａ袅烁髯缘乃饕?。這就是為什么 pop 會(huì)特別快。

push 方法也是一樣的。

循環(huán)

遍歷數(shù)組最古老的方式就是 for 循環(huán)：

let arr = ["Apple", "Orange", "Pear"];

for (let i = 0; i < arr.length; i++) {
  alert( arr[i] );
}

但對(duì)于數(shù)組來說還有另一種循環(huán)方式，for..of：

let fruits = ["Apple", "Orange", "Plum"];

// 遍歷數(shù)組元素
for (let fruit of fruits) {
  alert( fruit );
}

for..of 不能獲取當(dāng)前元素的索引，只是獲取元素值，但大多數(shù)情況是夠用的。而且這樣寫更短。

技術(shù)上來講，因?yàn)閿?shù)組也是對(duì)象，所以使用 for..in 也是可以的：

let arr = ["Apple", "Orange", "Pear"];

for (let key in arr) {
  alert( arr[key] ); // Apple, Orange, Pear
}

但這其實(shí)是一個(gè)很不好的想法。會(huì)有一些潛在問題存在：

1. ?for..in? 循環(huán)會(huì)遍歷 所有屬性，不僅僅是這些數(shù)字屬性。

在瀏覽器和其它環(huán)境中有一種稱為“類數(shù)組”的對(duì)象，它們 看似是數(shù)組。也就是說，它們有 length 和索引屬性，但是也可能有其它的非數(shù)字的屬性和方法，這通常是我們不需要的。for..in 循環(huán)會(huì)把它們都列出來。所以如果我們需要處理類數(shù)組對(duì)象，這些“額外”的屬性就會(huì)存在問題。


2. ?for..in? 循環(huán)適用于普通對(duì)象，并且做了對(duì)應(yīng)的優(yōu)化。但是不適用于數(shù)組，因此速度要慢 10-100 倍。當(dāng)然即使是這樣也依然非?？?。只有在遇到瓶頸時(shí)可能會(huì)有問題。但是我們?nèi)匀粦?yīng)該了解這其中的不同。

通常來說，我們不應(yīng)該用 for..in 來處理數(shù)組。

關(guān)于 “l(fā)ength”

當(dāng)我們修改數(shù)組的時(shí)候，length 屬性會(huì)自動(dòng)更新。準(zhǔn)確來說，它實(shí)際上不是數(shù)組里元素的個(gè)數(shù)，而是最大的數(shù)字索引值加一。

例如，一個(gè)數(shù)組只有一個(gè)元素，但是這個(gè)元素的索引值很大，那么這個(gè)數(shù)組的 length 也會(huì)很大：

let fruits = [];
fruits[123] = "Apple";

alert( fruits.length ); // 124

要知道的是我們通常不會(huì)這樣使用數(shù)組。

length 屬性的另一個(gè)有意思的點(diǎn)是它是可寫的。

如果我們手動(dòng)增加它，則不會(huì)發(fā)生任何有趣的事兒。但是如果我們減少它，數(shù)組就會(huì)被截?cái)?。該過程是不可逆的，下面是例子：

let arr = [1, 2, 3, 4, 5];

arr.length = 2; // 截?cái)嗟街皇?2 個(gè)元素
alert( arr ); // [1, 2]

arr.length = 5; // 又把 length 加回來
alert( arr[3] ); // undefined：被截?cái)嗟哪切?shù)值并沒有回來

所以，清空數(shù)組最簡(jiǎn)單的方法就是：arr.length = 0;。

new Array()

這是創(chuàng)建數(shù)組的另一種語法：

let arr = new Array("Apple", "Pear", "etc");

它很少被使用，因?yàn)榉嚼ㄌ?hào) [] 更短更簡(jiǎn)潔。而且，這種語法還有一個(gè)棘手的特性。

如果使用單個(gè)參數(shù)（即數(shù)字）調(diào)用 new Array，那么它會(huì)創(chuàng)建一個(gè) 指定了長(zhǎng)度，卻沒有任何項(xiàng) 的數(shù)組。

讓我們看看如何搬起石頭砸自己的腳:

let arr = new Array(2); // 會(huì)創(chuàng)建一個(gè) [2] 的數(shù)組嗎？

alert( arr[0] ); // undefined！沒有元素。

alert( arr.length ); // length 2

為了避免這種意外情況，我們通常使用方括號(hào)，除非我們真的知道自己在做什么。

多維數(shù)組

數(shù)組里的項(xiàng)也可以是數(shù)組。我們可以將其用于多維數(shù)組，例如存儲(chǔ)矩陣：

let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

alert( matrix[1][1] ); // 最中間的那個(gè)數(shù)

toString

數(shù)組有自己的 toString 方法的實(shí)現(xiàn)，會(huì)返回以逗號(hào)隔開的元素列表。

例如：

let arr = [1, 2, 3];

alert( arr ); // 1,2,3
alert( String(arr) === '1,2,3' ); // true

此外，我們?cè)囋囘\(yùn)行一下這個(gè)：

alert( [] + 1 ); // "1"
alert( [1] + 1 ); // "11"
alert( [1,2] + 1 ); // "1,21"

數(shù)組沒有 Symbol.toPrimitive，也沒有 valueOf，它們只能執(zhí)行 toString 進(jìn)行轉(zhuǎn)換，所以這里 [] 就變成了一個(gè)空字符串，[1] 變成了 "1"，[1,2] 變成了 "1,2"。

當(dāng) "+" 運(yùn)算符把一些項(xiàng)加到字符串后面時(shí)，加號(hào)后面的項(xiàng)也會(huì)被轉(zhuǎn)換成字符串，所以下一步就會(huì)是這樣：

alert( "" + 1 ); // "1"
alert( "1" + 1 ); // "11"
alert( "1,2" + 1 ); // "1,21"

不要使用 == 比較數(shù)組

JavaScript 中的數(shù)組與其它一些編程語言的不同，不應(yīng)該使用 == 運(yùn)算符比較 JavaScript 中的數(shù)組。

該運(yùn)算符不會(huì)對(duì)數(shù)組進(jìn)行特殊處理，它會(huì)像處理任意對(duì)象那樣處理數(shù)組。

讓我們回顧一下規(guī)則：

• 僅當(dāng)兩個(gè)對(duì)象引用的是同一個(gè)對(duì)象時(shí)，它們才相等 ?==?。
• 如果 ?==? 左右兩個(gè)參數(shù)之中有一個(gè)參數(shù)是對(duì)象，另一個(gè)參數(shù)是原始類型，那么該對(duì)象將會(huì)被轉(zhuǎn)換為原始類型，轉(zhuǎn)換規(guī)則如 對(duì)象 —— 原始值轉(zhuǎn)換 一章所述。
• ……?null ?和 ?undefined ?相等 ?==?，且各自不等于任何其他的值。

嚴(yán)格比較 === 更簡(jiǎn)單，因?yàn)樗粫?huì)進(jìn)行類型轉(zhuǎn)換。

所以，如果我們使用 == 來比較數(shù)組，除非我們比較的是兩個(gè)引用同一數(shù)組的變量，否則它們永遠(yuǎn)不相等。

例如：

alert( [] == [] ); // false
alert( [0] == [0] ); // false

從技術(shù)上講，這些數(shù)組是不同的對(duì)象。所以它們不相等。== 運(yùn)算符不會(huì)進(jìn)行逐項(xiàng)比較。

與原始類型的比較也可能會(huì)產(chǎn)生看似很奇怪的結(jié)果：

alert( 0 == [] ); // true

alert('0' == [] ); // false

在這里的兩個(gè)例子中，我們將原始類型和數(shù)組對(duì)象進(jìn)行比較。因此，數(shù)組 [] 被轉(zhuǎn)換為原始類型以進(jìn)行比較，被轉(zhuǎn)換成了一個(gè)空字符串 ''。

然后，接下來的比較就是原始類型之間的比較，如 類型轉(zhuǎn)換 一章所述：

// 在 [] 被轉(zhuǎn)換為 '' 后
alert( 0 == '' ); // true，因?yàn)?'' 被轉(zhuǎn)換成了數(shù)字 0

alert('0' == '' ); // false，沒有進(jìn)一步的類型轉(zhuǎn)換，是不同的字符串

那么，我們應(yīng)該如何對(duì)數(shù)組進(jìn)行比較呢？

很簡(jiǎn)單，不要使用 == 運(yùn)算符。而是，可以在循環(huán)中或者使用下一章中我們將介紹的迭代方法逐項(xiàng)地比較它們。

總結(jié)

數(shù)組是一種特殊的對(duì)象，適用于存儲(chǔ)和管理有序的數(shù)據(jù)項(xiàng)。

聲明：

// 方括號(hào) (常見用法)
let arr = [item1, item2...];

// new Array (極其少見)
let arr = new Array(item1, item2...);

調(diào)用 new Array(number) 會(huì)創(chuàng)建一個(gè)給定長(zhǎng)度的數(shù)組，但不含有任何項(xiàng)。

• ?length ?屬性是數(shù)組的長(zhǎng)度，準(zhǔn)確地說，它是數(shù)組最后一個(gè)數(shù)字索引值加一。它由數(shù)組方法自動(dòng)調(diào)整。
• 如果我們手動(dòng)縮短 ?length?，那么數(shù)組就會(huì)被截?cái)唷?/li>

獲取元素：

• 你可以通過元素的索引獲取元素，例如 ?arr[0]?
• 我們也可以使用允許負(fù)索引的 ?at(i)? 方法。對(duì)于負(fù)值的 ?i?，它會(huì)從數(shù)組的末尾往回?cái)?shù)。如果 ?i >= 0?，它的工作方式與 ?arr[i]? 相同。

我們可以通過下列操作以雙端隊(duì)列的方式使用數(shù)組：

• ?push(...items)? 在末端添加 ?items ?項(xiàng)。
• ?pop()? 從末端移除并返回該元素。
• ?shift()? 從首端移除并返回該元素。
• ?unshift(...items)? 從首端添加 ?items ?項(xiàng)。

遍歷數(shù)組的元素：

• ?for (let i=0; i<arr.length; i++)? — 運(yùn)行得最快，可兼容舊版本瀏覽器。
• ?for (let item of arr)? — 現(xiàn)代語法，只能訪問 items。
• ?for (let i in arr)? — 永遠(yuǎn)不要用這個(gè)。

比較數(shù)組時(shí)，不要使用 == 運(yùn)算符（當(dāng)然也不要使用 > 和 < 等運(yùn)算符），因?yàn)樗鼈儾粫?huì)對(duì)數(shù)組進(jìn)行特殊處理。它們通常會(huì)像處理任意對(duì)象那樣處理數(shù)組，這通常不是我們想要的。

但是，我們可以使用 for..of 循環(huán)來逐項(xiàng)比較數(shù)組。

在下一章 數(shù)組方法 中，我們將繼續(xù)學(xué)習(xí)數(shù)組，學(xué)習(xí)更多添加、移除、提取元素和數(shù)組排序的方法。

任務(wù)

---

數(shù)組被拷貝了嗎?

重要程度: 3

下面的代碼將會(huì)顯示什么？

let fruits = ["Apples", "Pear", "Orange"];

// 在“副本”里 push 了一個(gè)新的值
let shoppingCart = fruits;
shoppingCart.push("Banana");

// fruits 里面是什么？
alert( fruits.length ); // ?

---

解決方案

結(jié)果是 4:

let fruits = ["Apples", "Pear", "Orange"];

let shoppingCart = fruits;

shoppingCart.push("Banana");

alert( fruits.length ); // 4

這是因?yàn)閿?shù)組是對(duì)象。所以 shoppingCart 和 fruits 是同一數(shù)組的引用。

---

數(shù)組操作。

重要程度: 5

我們?cè)囋囅旅娴?5 個(gè)數(shù)組操作。

1. 創(chuàng)建一個(gè)數(shù)組 ?styles?，里面存儲(chǔ)有 “Jazz” 和 “Blues”。
2. 將 “Rock-n-Roll” 從數(shù)組末端添加進(jìn)去。
3. 用 “Classics” 替換掉數(shù)組最中間的元素。查找數(shù)組最中間的元素的代碼應(yīng)該適用于任何奇數(shù)長(zhǎng)度的數(shù)組。
4. 去掉數(shù)組的第一個(gè)值并顯示它。
5. 在數(shù)組前面添加 ?Rap ?和 ?Reggae?。

過程中的數(shù)組：

Jazz, Blues
Jazz, Blues, Rock-n-Roll
Jazz, Classics, Rock-n-Roll
Classics, Rock-n-Roll
Rap, Reggae, Classics, Rock-n-Roll

---

解決方案

let styles = ["Jazz", "Blues"];
styles.push("Rock-n-Roll");
styles[Math.floor((styles.length - 1) / 2)] = "Classics";
alert( styles.shift() );
styles.unshift("Rap", "Reggae");

---

在數(shù)組上下文調(diào)用

重要程度: 5

結(jié)果是什么？為什么？

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
});

arr[2](); // ?

---

解決方案

arr[2]() 調(diào)用從句法來看可以類比于 obj[method]()，與 obj 對(duì)應(yīng)的是 arr，與 method 對(duì)應(yīng)的是 2。

所以調(diào)用 arr[2] 函數(shù)也就是調(diào)用對(duì)象函數(shù)。自然地，它接收 this 引用的對(duì)象 arr 然后輸出該數(shù)組：

let arr = ["a", "b"];

arr.push(function() {
  alert( this );
})

arr[2](); // a,b,function(){...}

該數(shù)組有 3 項(xiàng)：最開始有兩個(gè)，后來添加進(jìn)來一個(gè)函數(shù)。

---

輸入數(shù)字求和

重要程度: 4

寫出函數(shù) sumInput()，要求如下：

• 使用 ?prompt ?向用戶索要值，并存在數(shù)組中。
• 當(dāng)用戶輸入了非數(shù)字、空字符串或者點(diǎn)擊“取消”按鈕的時(shí)候，問詢結(jié)束。
• 計(jì)算并返回?cái)?shù)組所有項(xiàng)之和。

P.S. ?0? 是有效的數(shù)字，不要因?yàn)槭?0 就停止問詢。

---

解決方案

請(qǐng)注意這個(gè)解決方案的細(xì)微但是很重要的細(xì)節(jié)。我們沒有在 prompt 后立即把 value 轉(zhuǎn)換成數(shù)字，因?yàn)樵趫?zhí)行 value = +value 之后，就沒辦法區(qū)分出空字符串（中斷標(biāo)志）和數(shù)字 0（合法輸入）了，所以要放到后面再處理。

function sumInput() {

  let numbers = [];

  while (true) {

    let value = prompt("A number please?", 0);

    // 應(yīng)該結(jié)束了嗎？
    if (value === "" || value === null || !isFinite(value)) break;

    numbers.push(+value);
  }

  let sum = 0;
  for (let number of numbers) {
    sum += number;
  }
  return sum;
}

alert( sumInput() );

---

最大子數(shù)組

重要程度: 2

輸入是以數(shù)字組成的數(shù)組，例如 arr = [1, -2, 3, 4, -9, 6].

任務(wù)是：找出所有項(xiàng)的和最大的 arr 數(shù)組的連續(xù)子數(shù)組。

寫出函數(shù) getMaxSubSum(arr)，用其找出并返回最大和。

例如：

getMaxSubSum([-1, 2, 3, -9]) == 5（高亮項(xiàng)的加和）
getMaxSubSum([2, -1, 2, 3, -9]) == 6
getMaxSubSum([-1, 2, 3, -9, 11]) == 11
getMaxSubSum([-2, -1, 1, 2]) == 3
getMaxSubSum([100, -9, 2, -3, 5]) == 100
getMaxSubSum([1, 2, 3]) == 6（所有項(xiàng)的和）

如果所有項(xiàng)都是負(fù)數(shù)，那就一個(gè)項(xiàng)也不?。ㄗ訑?shù)組是空的），所以返回的是 0：

getMaxSubSum([-1, -2, -3]) = 0

請(qǐng)嘗試想出一個(gè)快速的解決方案：復(fù)雜度可以是 O(n²)，有能力達(dá)到 O(n) 則更好。

---

解決方案

慢的解決方案

我們可以計(jì)算所有可能的子集的和。

最簡(jiǎn)單的方法就是獲取每個(gè)元素然后計(jì)算從它開始所有子數(shù)組的和。

以 [-1, 2, 3, -9, 11] 為例：

// 從 -1 開始：
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// 從 2 開始：
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// 從 3 開始：
3
3 + (-9)
3 + (-9) + 11

// 從 -9 開始：
-9
-9 + 11

// 從 11 開始：
11

這樣寫出來的代碼實(shí)際上是一個(gè)嵌套循環(huán)：外部循環(huán)遍歷數(shù)組所有元素，內(nèi)部循環(huán)計(jì)算從當(dāng)前元素開始的所有子數(shù)組各自的和。

function getMaxSubSum(arr) {
  let maxSum = 0; // 如果沒有取到任何元素，就返回 0

  for (let i = 0; i < arr.length; i++) {
    let sumFixedStart = 0;
    for (let j = i; j < arr.length; j++) {
      sumFixedStart += arr[j];
      maxSum = Math.max(maxSum, sumFixedStart);
    }
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100

該方案的時(shí)間復(fù)雜度是 O(n²)。也就是說，如果我們把數(shù)組大小增加 2 倍，那么算法的運(yùn)行時(shí)間將會(huì)延長(zhǎng)4倍。

對(duì)于大型數(shù)組（1000，10000 或者更多項(xiàng)）這種算法會(huì)導(dǎo)致嚴(yán)重的時(shí)間消耗。

快的解決方案

讓我們遍歷數(shù)組，將當(dāng)前局部元素的和保存在變量 s 中。如果 s 在某一點(diǎn)變成負(fù)數(shù)了，就重新分配 s=0。所有 s 中的最大值就是答案。

如果文字描述不太好理解，就直接看下面的代碼吧，真的很短：

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) { // arr 中的每個(gè) item
    partialSum += item; // 將其加到 partialSum
    maxSum = Math.max(maxSum, partialSum); // 記住最大值
    if (partialSum < 0) partialSum = 0; // 如果是負(fù)數(shù)就置為 0
  }

  return maxSum;
}

alert( getMaxSubSum([-1, 2, 3, -9]) ); // 5
alert( getMaxSubSum([-1, 2, 3, -9, 11]) ); // 11
alert( getMaxSubSum([-2, -1, 1, 2]) ); // 3
alert( getMaxSubSum([100, -9, 2, -3, 5]) ); // 100
alert( getMaxSubSum([1, 2, 3]) ); // 6
alert( getMaxSubSum([-1, -2, -3]) ); // 0

該算法只需要遍歷 1 輪數(shù)組，所以時(shí)間復(fù)雜度是 O(n)。

你也可以在這獲取更多該算法的細(xì)節(jié)信息：最大子數(shù)組問題。如果還是不明白，那就調(diào)試上面的例子，觀察它是怎樣工作的，說得再多也沒有自己去調(diào)試好使。

function getMaxSubSum(arr) {
  let maxSum = 0;
  let partialSum = 0;

  for (let item of arr) {
    partialSum += item;
    maxSum = Math.max(maxSum, partialSum);
    if (partialSum < 0) partialSum = 0;
  }
  return maxSum;
}