数据结构与算法 | 数组(Array)-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法 | 数组(Array)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

数组(Array)

数组（Array）应该是最基础的数据结构之一，它由相同类型的元素组成的集合，并按照一定的顺序存储在内存中。每个元素都有一个唯一的索引，可以用于访问该元素。

	// java 数组示例
	int[] numbers1 = {2,0,2,3,9,23};
	// 或者
	int[] numbers2 = new int[6];

基本概念

数组基本概念 —— 数组索引、数组元素、数组长度

数组索引（Index）：数组中的每个元素都有一个唯一的整数索引，从0开始计数。索引用于访问数组中的元素。
数组元素（Element）：数组中的元素必须是相同类型的数据，可以是整数、浮点数、字符、对象等。
数组长度（Length）：数组的长度是指数组中包含的元素数量。

数据结构与算法 | 数组(Array)

其具备一些性质：

连续存储（Contiguous Memory）：数组中的元素在内存中是连续存储的，这意味着通过索引可以直接计算出元素的地址。
随机访问时间（Constant Time Access）：由于元素的连续存储和索引的存在，通过索引访问数组中的某个元素通常只需要常数时间O(1)。（ PS: 什么叫随机访问？ 是计算机领域的一个重要概念，指的是能够以大致相等的时间访问存储介质中的任何数据元素，而不受其物理存储位置顺序的限制。通俗点说，随便获取任意一个元素。）

基本应用（Basic）

数组的结构本身比较简单，在解决常见面试算法问题中灵活应用数组索引来访问数据是关键。

Leetcode 26. 删除有序数组中的重复项【简单】

给你一个非严格递增排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

数据结构与算法 | 数组(Array)

LeetCode 674. 最长连续递增序列【简单】

给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。

连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

数据结构与算法 | 数组(Array)

双指针（Two Pointers）

一些资料上也有说双指针算法，笔者看来更倾向于是一种技巧，定义的两个索引指针通过操作两个索引指针来获取问题答案。（PS：为什么这里叫指针？指针更多的是C语言中的概念，最早C语言解决算法问题比较多。）

根据指针移动或者所指位置不同，也有不少其他种分类的说法比如：对撞指针、快慢指针、分离指针等等；但其技巧本质都是在于操作两个指针索引，大可不必严格定义这些名称，需要的是抓住重点操作两个指针。

LeetCode 167. 两数之和 II - 输入有序数组【中等】

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

数据结构与算法 | 数组(Array)

LeetCode 15. 三数之和【中等】

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

数据结构与算法 | 数组(Array)