数组简介

集合、列表和数组

集合

• 集合里的元素类型不一定相同（可以同时有String和int）
• 集合里的元素没有顺序（因此，不会有在集合里找第一个元素的说法）

列表

• 列表（又称线性列表）的定义为：是一种数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。
• 列表的概念是在集合的特征上形成的，它具有顺序，且长度是可变的。
  • 里面的元素类型可以不同
  • 长度是可变的，可以增加或者删除元素
• 常见形式
  • 数组
  • 链表
  • 栈
  • 队列

数组

• 数组是列表的实现方式之一
• JAVA中数组中的元素类型必须保持一致
• 数组和列表的区别
  • 数组会有索引，用来标识每项数据在数组中的位置；而列表中没有索引
  • 数组中的元素在内存中是连续存储的，且每个元素占用相同大小的内存；而列表中的元素在内存中可能彼此相邻，也可能不相邻。

集合、列表和数组的不同归纳

• 集合和列表内可以有任意类型的元素，数组只能有一种
• 集合内的元素没有顺序，列表和数组内的元素有顺寻（按照一定的线性顺序排列而成）
• 数组中的元素在内存中是连续存储的，列表在内存中不是

数组的使用

读取元素

• 通过访问索引的方式来读取的，注意：索引一般从 0 开始。
  • 例：找a数组的第三个元素即a[2]，2为索引
• 数组在内存的存储方式：计算机会在内存中为数组申请一段连续的空间，并且会记下索引为0处的内存地址；当内存地址加上索引值时，即目标元素的地址。
  • 例：数组int a[5]={1,2,3,4,5},索引为 0 处的内存地址为2000。则a[2]的地址为2000+2=2002，对应目标元素为3

• 数组访问元素的时间复杂度为O（1）

查找元素

• 最简单:从数组开头，循环向后查找；当出现查找的元素时停止
• 时间复杂度为 O(N)，N为数组的长度N

插入元素

• 将元素插入到数组的末尾，只需要一步
  • 即计算机通过数组的长度和位置计算出即将插入元素的内存地址，然后将该元素插入到指定位置即可。
• 将元素插入到数组中除了末尾以外的其他位置，需要两步
  • 第一步：腾位，即将元素要插入的目标位置上的元素及后面的元素往后移
  • 第二部：插入，即将元素放到目标位置
• 第一种插入的时间复杂度为O(1)；第二种的时间复杂度为O(N)，N为数组的长度。
  • 如果频繁地对数组元素进行第二种的插入操作，会造成时间的浪费，建议使用链表

删除元素

• 删除元素与插入元素到非末尾位置的操作类似，也是两步
  • 删除掉数组中目标位置的元素
  • 数组中在该位置会空缺，而数组中的元素在内存中是连续的，这就使得后面的元素需对该位置进行填补操作，即将该位置之后的元素全部往前移动。
• 时间复杂度为O(N)，N为数组的长度。

例题：寻找数组的中心索引（https://leetcode.cn/problems/find-the-middle-index-in-array/）

• 题目内容:给你一个整数数组 nums ，请计算数组的 中心下标 。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
• 运行成功代码：
  很直接的做法，从头开始找，根据每次循环的i作为划分，分别计算左侧和右侧的值，最后判断是否相等，相等就直接当次循环返回对应的i；一个都没找到就返回-1。

class Solution {
    public int findMiddleIndex(int[] nums) {
        int middleIndex=-1;
        for(int i=0;i<nums.length;i++){
            int left=0;
            int right=0;
            for(int j=0;j<i;j++){
                left+=nums[j];
            }
            for(int k=i+1;k<nums.length;k++){
                right+=nums[k];
            }
            if(left==right){
                middleIndex=i;
                break;
            }
        }
        return middleIndex;
    }
}

• 优化代码
  相较于前面的代码，该代码优化的地方在于：一开始将整个数组的数加起来，用于后面的计算；后面的计算中，将原本单独计算的右侧总数的循环删去，改为和左侧实时判断是否相等，相等即立即返回i。

class Solution {
    public int findMiddleIndex(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int left = 0;
        for (int i=0; i<nums.length; i++) {
            if(left+left == sum-nums[i]){
                return i;
            }
            left+=nums[i];
        }
        return -1;
    }
}