2023 年 1 月 24 日

数组

对象允许你存储键控值集合。这很好。

但我们经常发现我们需要一个有序集合，其中我们有第 1 个、第 2 个、第 3 个元素，依此类推。例如，我们需要存储一个列表：用户、商品、HTML 元素等。

在这里使用对象不方便，因为它不提供管理元素顺序的方法。我们不能在现有属性“之间”插入一个新属性。对象根本不适合这种用途。

存在一个名为 Array 的特殊数据结构，用于存储有序集合。

声明

创建空数组有两种语法

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

几乎所有时间都使用第二个语法。我们可以在括号中提供初始元素

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

数组元素从零开始编号。

我们可以在方括号中通过其编号获取一个元素

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

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

我们可以替换一个元素

fruits[2] = 'Pear'; // now ["Apple", "Orange", "Pear"]

…或者向数组中添加一个新元素

fruits[3] = 'Lemon'; // now ["Apple", "Orange", "Pear", "Lemon"]

数组中元素的总数是其length

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

alert( fruits.length ); // 3

我们还可以使用alert来显示整个数组。

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

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

数组可以存储任何类型的元素。

例如

// mix of values
let arr = [ 'Apple', { name: 'John' }, true, function() { alert('hello'); } ];

// get the object at index 1 and then show its name
alert( arr[1].name ); // John

// get the function at index 3 and run it
arr[3](); // hello

数组就像对象一样，可以以逗号结尾

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

“尾随逗号”样式使得插入/删除项目变得更加容易，因为所有行都变得相似。

使用“at”获取最后一个元素

这是最近添加到该语言中的内容。旧浏览器可能需要polyfills。

假设我们想要数组的最后一个元素。

一些编程语言允许使用负索引来实现相同目的，比如fruits[-1]。

然而，在 JavaScript 中它不起作用。结果将是undefined，因为方括号中的索引被逐字处理。

我们可以显式计算最后一个元素索引，然后访问它：fruits[fruits.length - 1]。

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

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

有点麻烦，不是吗？我们需要写两次变量名。

幸运的是，有一个更简洁的语法：fruits.at(-1)

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

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

换句话说，arr.at(i)

与arr[i]完全相同，如果i >= 0。
对于i的负值，它从数组末尾后退。

方法 pop/push、shift/unshift

队列是数组最常见的用法之一。在计算机科学中，这意味着一个有序的元素集合，它支持两个操作

push将一个元素附加到末尾。
shift从开头获取一个元素，推进队列，以便第 2 个元素变为第 1 个元素。

数组支持这两个操作。

在实践中，我们非常需要它。例如，需要在屏幕上显示的消息队列。

数组还有另一种用例——名为堆栈的数据结构。

它支持两个操作

push向末尾添加一个元素。
pop从末尾获取一个元素。

因此，新元素总是从“末尾”添加或获取。

栈通常被描述为一叠卡片：新卡片被添加到顶部或从顶部取出

对于栈，最后压入的项目首先被接收，这也称为 LIFO（后进先出）原则。对于队列，我们有 FIFO（先进先出）。

JavaScript 中的数组既可以作为队列，也可以作为栈。它们允许您添加/删除元素，无论是从开头还是结尾。

在计算机科学中，允许这样做的数据结构称为双端队列。

处理数组末尾的方法

pop

提取数组的最后一个元素并返回它

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

alert( fruits.pop() ); // remove "Pear" and alert it

alert( fruits ); // Apple, Orange

fruits.pop() 和 fruits.at(-1) 都返回数组的最后一个元素，但 fruits.pop() 也通过删除它来修改数组。

push

将元素附加到数组末尾

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

fruits.push("Pear");

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

调用 fruits.push(...) 等于 fruits[fruits.length] = ...。

处理数组开头的的方法

shift

提取数组的第一个元素并返回它

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

alert( fruits.shift() ); // remove Apple and alert it

alert( fruits ); // Orange, Pear

unshift

将元素添加到数组开头

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

fruits.unshift('Apple');

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

方法 push 和 unshift 可以一次添加多个元素

let fruits = ["Apple"];

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

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

内部

数组是一种特殊类型的对象。用于访问属性 arr[0] 的方括号实际上来自对象语法。这与 obj[key] 本质上相同，其中 arr 是对象，而数字用作键。

它们扩展了对象，提供了特殊方法来处理有序的数据集合，还提供了 length 属性。但从本质上来说，它仍然是一个对象。

请记住，JavaScript 中只有八种基本数据类型（有关更多信息，请参阅数据类型章节）。数组是一个对象，因此表现得像一个对象。

例如，它是通过引用复制的

let fruits = ["Banana"]

let arr = fruits; // copy by reference (two variables reference the same array)

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

arr.push("Pear"); // modify the array by reference

alert( fruits ); // Banana, Pear - 2 items now

…但让数组真正特别的是它们的内部表示。引擎尝试将其元素存储在连续的内存区域中，一个接一个，就像本章中的插图中描述的那样，还有其他优化，可以让数组工作得非常快。

但如果我们停止将数组作为“有序集合”处理，而是开始像对待普通对象一样处理它，那么所有这些都会中断。

例如，从技术上讲，我们可以这样做

          let fruits = []; // make an array

fruits[99999] = 5; // assign a property with the index far greater than its length

fruits.age = 25; // create a property with an arbitrary name

这是可能的，因为数组本质上是对象。我们可以向它们添加任何属性。

但引擎会看到我们正在像对待普通对象一样处理数组。特定于数组的优化不适合此类情况，并且会被关闭，它们的优点会消失。

滥用数组的方法

添加非数字属性，如 arr.test = 5。
创建孔洞，例如：添加 arr[0] 然后添加 arr[1000]（它们之间没有任何内容）。
以相反的顺序填充数组，例如 arr[1000]、arr[999] 等。

请将数组视为处理有序数据的特殊结构。它们为此提供了特殊方法。JavaScript 引擎内部对数组进行了精心调整，以处理连续有序数据，请使用这种方式。如果你需要任意键，则很有可能实际上需要一个常规对象 {}。

性能

方法 push/pop 运行速度很快，而 shift/unshift 速度较慢。

为什么使用数组的末尾比使用其开头更快？让我们看看执行期间发生了什么

fruits.shift(); // take 1 element from the start

仅获取和移除具有索引 0 的元素是不够的。其他元素也需要重新编号。

shift 操作必须执行 3 项操作

移除具有索引 0 的元素。
将所有元素向左移动，将它们从索引 1 重新编号为 0，从 2 重新编号为 1，依此类推。
更新 length 属性。

数组中的元素越多，移动它们所需的时间就越多，内存操作也就越多。

unshift 也会发生类似的情况：要向数组开头添加一个元素，我们首先需要将现有元素向右移动，增加它们的索引。

push/pop 又如何呢？它们不需要移动任何内容。要从末尾提取一个元素，pop 方法会清除索引并缩短 length。

pop 操作的动作

fruits.pop(); // take 1 element from the end

pop 方法不需要移动任何内容，因为其他元素会保留其索引。这就是它非常快的原因。

push 方法的情况类似。

循环

循环数组项最古老的方法之一是对索引使用 for 循环

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

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

但对于数组，还有另一种形式的循环，即 for..of

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

// iterates over array elements
for (let fruit of fruits) {
  alert( fruit );
}

for..of 无法访问当前元素的编号，只能访问其值，但在大多数情况下，这已经足够了。而且它更简洁。

从技术上讲，由于数组是对象，因此也可以使用 for..in

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

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

但这实际上是一个坏主意。它存在潜在问题

循环 for..in 会迭代所有属性，而不仅仅是数字属性。

浏览器和其他环境中存在所谓的“类数组”对象，它们看起来像数组。也就是说，它们具有 length 和索引属性，但它们也可能具有其他非数字属性和方法，而这些属性和方法通常不是必需的。但 for..in 循环会列出它们。因此，如果我们需要使用类数组对象，那么这些“额外”属性可能会成为问题。
for..in 循环针对通用对象进行了优化，而不是数组，因此速度慢 10-100 倍。当然，它仍然非常快。速度提升可能仅在瓶颈中很重要。但我们仍应意识到这种差异。

通常，我们不应将 for..in 用于数组。

关于“length”的一句话

当我们修改数组时，length 属性会自动更新。准确地说，它实际上不是数组中值的计数，而是最大的数字索引加一。

例如，具有较大索引的单个元素会产生较大的长度

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

alert( fruits.length ); // 124

请注意，我们通常不会像这样使用数组。

关于 length 属性的另一个有趣之处在于它是可写的。

如果我们手动增加它，则不会发生任何有趣的事情。但如果我们减少它，数组将被截断。该过程是不可逆的，以下为示例

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

arr.length = 2; // truncate to 2 elements
alert( arr ); // [1, 2]

arr.length = 5; // return length back
alert( arr[3] ); // undefined: the values do not return

因此，清除数组的最简单方法是：arr.length = 0;。

new Array()

还有一种语法可以创建数组

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

它很少使用，因为方括号 [] 较短。此外，它还具有一个棘手的功能。

如果 new Array 被调用，并且只有一个参数是一个数字，那么它将创建一个数组，其中没有项目，但具有给定的长度。

让我们看看如何搬起石头砸自己的脚

let arr = new Array(2); // will it create an array of [2] ?

alert( arr[0] ); // undefined! no elements.

alert( arr.length ); // length 2

为了避免此类意外，我们通常使用方括号，除非我们真的知道自己在做什么。

多维数组

数组可以包含也是数组的项目。我们可以将它用于多维数组，例如存储矩阵

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

alert( matrix[1][1] ); // 5, the central element

toString

数组有自己的 toString 方法实现，该方法返回元素的逗号分隔列表。

例如

let arr = [1, 2, 3];

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

此外，我们尝试一下

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

数组没有 Symbol.toPrimitive，也没有可行的 valueOf，它们只实现 toString 转换，因此此处 [] 变为空字符串，[1] 变为 "1"，[1,2] 变为 "1,2"。

当二进制加号 "+" 运算符向字符串添加内容时，它也会将其转换为字符串，因此下一步如下所示

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

不要用 == 比较数组

与某些其他编程语言不同，JavaScript 中的数组不应与运算符 == 进行比较。

此运算符对数组没有特殊处理，它将数组作为任何对象一样处理。

让我们回顾一下规则

只有当两个对象是对同一对象的引用时，它们才相等 ==。
如果 == 的其中一个参数是对象，而另一个是原始类型，则对象会转换为原始类型，如章节对象到原始类型转换中所述。
…除了 null 和 undefined，它们彼此 == 相等，并且不等于其他任何内容。

严格比较 === 甚至更简单，因为它不转换类型。

因此，如果我们使用 == 比较数组，它们永远不会相同，除非我们比较引用完全相同数组的两个变量。

例如

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

从技术上讲，这些数组是不同的对象。因此，它们不相等。== 运算符不执行逐项比较。

与原始类型的比较也可能产生看似奇怪的结果

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

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

在这里，在这两种情况下，我们都将一个原始类型与一个数组对象进行比较。因此，数组 [] 会转换为原始类型以进行比较，并变为空字符串 ''。

然后，比较过程将继续使用原始类型，如章节类型转换中所述

// after [] was converted to ''
alert( 0 == '' ); // true, as '' becomes converted to number 0

alert('0' == '' ); // false, no type conversion, different strings

那么，如何比较数组？

很简单：不要使用 == 运算符。相反，在循环中逐项比较它们，或使用下一章中解释的迭代方法。

总结

数组是一种特殊类型的对象，适用于存储和管理有序数据项。

声明

          // square brackets (usual)
let arr = [item1, item2...];

// new Array (exceptionally rare)
let arr = new Array(item1, item2...);
        

对 new Array(number) 的调用会创建一个具有给定长度的数组，但不包含元素。

length 属性是数组长度，或者更准确地说，是其最后一个数字索引加一。它由数组方法自动调整。
如果我们手动缩短 length，数组将被截断。

获取元素

我们可以通过其索引获取元素，例如 arr[0]
我们还可以使用 at(i) 方法，该方法允许使用负索引。对于 i 的负值，它会从数组末尾后退。如果 i >= 0，则其工作方式与 arr[i] 相同。

我们可以使用以下操作将数组用作双端队列

push(...items) 将 items 添加到末尾。
pop() 从末尾移除元素并返回它。
shift() 从开头移除元素并返回它。
unshift(...items) 将 items 添加到开头。

循环遍历数组元素

for (let i=0; i<arr.length; i++) – 运行速度最快，兼容旧浏览器。
for (let item of arr) – 仅适用于项目的现代语法，
for (let i in arr) – 永远不要使用。

要比较数组，请不要使用 == 运算符（以及 >、< 等），因为它们对数组没有特殊处理。它们将数组处理为任何对象，而这通常不是我们想要的。

相反，你可以使用 for..of 循环逐项比较数组。

我们将在下一章数组方法中继续学习数组，并研究更多用于添加、删除、提取元素和对数组进行排序的方法。

任务

数组是否被复制？

这段代码将显示什么？

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

// push a new value into the "copy"
let shoppingCart = fruits;
shoppingCart.push("Banana");

// what's in fruits?
alert( fruits.length ); // ?
        

结果是 4

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

let shoppingCart = fruits;

shoppingCart.push("Banana");

alert( fruits.length ); // 4

这是因为数组是对象。因此 shoppingCart 和 fruits 都是对同一数组的引用。

数组操作。

我们尝试 5 个数组操作。

创建一个包含项“爵士”和“布鲁斯”的数组 styles。
将“摇滚”附加到末尾。
用“古典”替换中间的值。用于查找中间值的代码应适用于任何长度为奇数的数组。
剥离数组的第一个值并显示它。
将 Rap 和 Reggae 前置到数组。

正在处理的数组

          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");

在数组上下文中调用

结果是什么？为什么？

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

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

arr[2](); // ?
        

调用 arr[2]() 在语法上是老式的 obj[method]()，在 obj 的角色中，我们有 arr，在 method 的角色中，我们有 2。

因此，我们调用函数 arr[2] 作为对象方法。自然地，它接收 this 引用对象 arr 并输出数组

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

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

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

该数组有 3 个值：最初有 2 个，加上该函数。

求和输入数字

编写函数 sumInput()，该函数

使用 prompt 向用户询问值，并将值存储在数组中。
当用户输入非数字值、空字符串或按“取消”时，结束询问。
计算并返回数组项的总和。

附注：零 0 是一个有效数字，请不要在零时停止输入。

运行演示

请注意解决方案的微妙但重要的细节。我们不会在 prompt 之后立即将 value 转换为数字，因为在 value = +value 之后，我们将无法区分空字符串（停止标志）和零（有效数字）。我们稍后这样做。

function sumInput() {

  let numbers = [];

  while (true) {

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

    // should we cancel?
    if (value === "" || value === null || !isFinite(value)) break;

    numbers.push(+value);
  }

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

alert( sumInput() );

最大子数组

输入是一个数字数组，例如 arr = [1, -2, 3, 4, -9, 6]。

任务是：找到 arr 的连续子数组，其项的总和最大。

编写函数 getMaxSubSum(arr)，该函数将返回该总和。

例如

          getMaxSubSum([-1, 2, 3, -9]) == 5 (the sum of highlighted items)
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 (take all)
        

如果所有项都为负，则表示我们不取任何项（子数组为空），因此总和为零

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

请尝试考虑一个快速的解决方案：O(n²)，甚至 O(n)（如果你能的话）。

在沙盒中打开带有测试的代码。

慢速解法

我们可以计算所有可能的子和。

最简单的方法是获取每个元素并计算从它开始的所有子数组的和。

例如，对于 [-1, 2, 3, -9, 11]

          // Starting from -1:
-1
-1 + 2
-1 + 2 + 3
-1 + 2 + 3 + (-9)
-1 + 2 + 3 + (-9) + 11

// Starting from 2:
2
2 + 3
2 + 3 + (-9)
2 + 3 + (-9) + 11

// Starting from 3:
3
3 + (-9)
3 + (-9) + 11

// Starting from -9
-9
-9 + 11

// Starting from 11
11
        

代码实际上是一个嵌套循环：外部循环遍历数组元素，内部循环计算从当前元素开始的子和。

function getMaxSubSum(arr) {
  let maxSum = 0; // if we take no elements, zero will be returned

  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

该解法的时间复杂度为 O(n²)。换句话说，如果我们把数组大小增加 2 倍，算法将运行 4 倍的时间。

对于大型数组（1000、10000 或更多项），此类算法会导致严重的迟缓。

快速解法

让我们遍历数组，并在变量 s 中保留元素的当前部分和。如果 s 在某个时刻变为负数，则将 s=0 赋值给它。所有此类 s 的最大值将是答案。

如果描述过于模糊，请查看代码，它足够简洁

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

  for (let item of arr) { // for each item of arr
    partialSum += item; // add it to partialSum
    maxSum = Math.max(maxSum, partialSum); // remember the maximum
    if (partialSum < 0) partialSum = 0; // zero if negative
  }

  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 次数组遍历，因此时间复杂度为 O(n)。

你可以在此处找到有关该算法的更详细信息：最大子数组问题。如果仍然不明白为什么这样做有效，请根据上述示例跟踪算法，看看它是如何工作的，这比任何文字都更好。

在沙盒中打开带有测试的解法。

教程地图

评论之前请阅读此内容…

慢速解法

快速解法

章节

课程导航