一、数据结构的基本介绍
数据结构是计算机专业非常核心的一门基础课程，同时也是程序竞赛、企业笔试面试、研究生考试当中高频考察的重点内容，它和程序设计基础、离散数学、线性代数等课程紧密关联，是后续学习操作系统、数据库、大数据、人工智能、Web开发等方向的底层基础。
从定义上来说：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素并不是孤立零散存在的，元素与元素之间具备特定的逻辑关系，这些关系共同构成对应的结构。简单概括公式：
数据结构 = 数据元素 + 元素之间的结构（关系）
我们可以把数据结构理解为带结构的数据元素集合。就好比做菜，光有食材调料（对应数据）还不够，还需要烹饪的组织方式（对应结构），二者结合才能完成完整的菜品。著名图灵奖得主Pascal之父尼古拉斯·沃斯提出经典公式：
程序 = 算法 + 数据结构
数据结构负责解决数据如何组织存放，算法负责解决处理数据的步骤逻辑，二者不可分割。如果数据组织方式不合理，即便算法写得再好，程序的运行效率也会很差。
按照数据元素之间逻辑关系，数据结构分为两大类：

1. 线性结构：包含数组、链表、栈、队列。元素呈现一条线性序列，除首尾元素之外，每一个数据元素仅有唯一的前驱元素和后继元素。
2. 非线性结构：包含树、图。元素不再是简单一条直线，可以出现分支、多对多网状关系，一个元素可以对应多个前驱或者后继。
   学习数据结构的意义：面对业务问题，选择合适的数据结构存储数据，能够大幅降低时间、空间开销，写出更高效的程序。
   二、数组的基本概念
   数组属于最基础的线性顺序存储结构。
   定义：数组是n（n＞1）个相同类型的数据元素 a_1,a_2…a_n 组成的有限序列，逻辑表达：A=(a_1,a_2,…,a_n)，其中 a_i 代表数组A当中第i个元素。

1.内存与随机访问特性
数组在内存当中占用连续的一块存储单元，这是数组最核心的特征。
假设第一个元素 a_1 的内存地址为 LOC(a_1)，每个元素占用k个存储单元，那么数组中任意元素 a_i 的地址计算公式：
LOC(a_i)=LOC(a_1)+(i-1)*k
依靠这个公式，计算机可以直接通过下标计算出任意元素的内存地址，不需要从头逐个遍历，这就是随机访问能力。我们可以直接通过下标读取任意位置元素，访问速度O(1)，这是数组最大优势。

2.数组的增删特点

1. 删除数组尾部元素：只需要修改记录数组有效元素个数（size），不需要移动任何元素，操作开销很小。逻辑上直接忽略末尾元素即可，原始内存数据可以保留，不再参与运算。
2. 删除数组中间位置i的元素：

• 第一步：合法性校验，下标必须满足 0≤i≤len(nums)-1，下标越界不能操作；
• 第二步：把i位置后面所有元素，依次向前移动一个位置，覆盖掉被删除的元素；
• 第三步：修改数组有效元素计数size。
  中间插入元素逻辑同理，需要把后续元素整体向后挪，腾出空位。

3.Python中的数组（列表list）
Python语言没有传统意义固定长度的静态数组，列表list充当数组的角色。

• 基础写法：方括号包裹，元素逗号隔开，例如 a=[2,5,3,1,4] 作为一维数组； b=[[2,3,8],[5,3,4]] 作为二维数组。
• Python列表比较特殊：它内部元素允许存放不同数据类型，底层是动态数组，可以自动扩容，不需要手动指定固定长度。
• 底层依旧延续顺序存储的核心特征：下标访问速度快；但是中间插入删除依旧会造成元素移动，开销大。

4.顺序查找（线性查找）
顺序查找是针对数组最简单的查找算法，也叫线性查找。
基本思路：从数组一端开始逐个扫描元素，拿每一个元素和目标值对比；匹配成功直接返回对应位置；扫描完所有元素依旧找不到目标，则查找失败。
顺序查找不需要数组有序，但是时间复杂度O(n)，数据量大的时候效率很差。
三、Leetcode 704题解
左闭右闭区间

左闭右开区间

题解