算法学习笔记（2）

数组，链表，跳表

数组

数组是经常会用到的一种数据结构，它的特点就是内存地址连续。下面说一下关于数组的一些操作。

数组的插入

如上图，如果我们想往数组中插入一个元素的话，在插入位置后的所有元素，都需要向后进行移动，在最好的情况下，是在数组的最后一个位置插入元素，此时不需要移动任何元素，在最坏的情况下，是在数组的首位置插入元素，整个数组都需要向后进行移动。所以移动的次数是和数组的元素个数息息相关的，在元素个数为n的情况下，平均下来也要差不多移动n/2次，所以数组的插入时间复杂度为O(n)

数组的删除

删除操作和插入操作差不多，也是需要进行元素的移动，在最好的情况下是删除数组最后一个元素，此时不需要移动元素。最坏的情况下是删除数组的第一个元素，此时整体都需要移动。所以数组的删除时间复杂度也是O(n)

链表

链表的出现是为了改善数组的，链表的结构通常如下

链表中的每一个元素通常叫做节点，节点通常有自己的值value，以及一个指针，这个指针是指向它的下一个节点的。最开始的节点叫做head头结点，最后的节点叫做tail尾节点。

链表的插入

链表的插入操作很简单，新插入的节点位置的上一个节点的next指针指向该新节点，新节点的next指针指向原有的节点的下一个节点即可，如上图两条红线所示。这样就可以插入一个新的节点。

节点的插入只需要操作两次指针的指向即可，是常数级别的，所以链表的插入操作时间复杂度为O(1)

链表的删除

删除操作和插入差不多，也是只需要变换指针的指向即可，也是常数级别的。所以链表的删除操作时间复杂度是O(1)

tips：

和数组对比起来，链表的插入和删除的效率要很多，时间复杂度都是O(1)，但是要随机访问链表中的元素，就没那么简单和容易了，必须从head节点开始往后一步一步的进行查找，所以相比于数组，链表的随机访问时间复杂度是O(n)，而数组的随机访问，因为有index的存在，它的时间复杂度就是O(1)

跳表

跳表是从链表演化而来的，我们知道链表的查询时间复杂度是O(n)，如何能够对链表进行加速呢？

一个简单的想法，就是对链表添加尾指针，这样当查询链表尾部元素的时候，就可以使用尾指针快速的定位，而不是从头节点依次向后遍历。同样的思路，我们还可以在链表的中部添加中指针，这样当访问链表中部元素的时候，也会更加的快速。根据这个思想，就衍生出了跳表的概念。

所谓链表的跳表，就是通过升维+空间换时间的思想得来的，它的具体表现就是通过索引实现的。如下图。

在原始链表的基础上，每跳一个节点，添加一个索引，当我们访问原始链表中的某个具体元素的时候，要先访问索引，这样能跳过大部分无用的节点，加快访问速度。

有一级索引，就有二级索引，如下图

二级索引在一级索引的基础上，再次进行跳跃，每跳一个一级节点索引，就添加一个二级索引，当我们访问原始链表中的某个具体元素的时候，要先访问二级索引，然后再访问一级索引，这样能跳过更多无用的节点，加快访问速度。

假设链表的节点数为n，由此不难看出，一级索引的个数是n/2，二级索引的个数是n/4，依此类推，k级索引的个数是n/(2^k)。假设索引有h级，且最高级的索引有2个节点，即n/(2^h)=2，从而得到h=log2(n)-1。那么跳表查询的时间复杂度就是O(logn)

高频算法题

移动零

源自leetcode第283题

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例2:
输入: nums = [0]
输出: [0]

此题要求在不复制数组的情况下完成这个操作，那么就不能使用额外的数组作为存储介质，得考虑使用相关的索引对数据操作进行记录。下面是一种解题方式。

class Solution {
    public void moveZeroes(int[] nums) {
        // 用于记录移动到数组前面最后一个元素的位置
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                // 遇到非0元素，将其移动到数组的前面
                nums[j] = nums[i];
                // 当前位置补0
                if (i != j) {
                    nums[i] = 0;
                }
                // 指针后移，为下一个移动到前面的元素留位置
                j++;
            }
        }
    }
}

分步骤剖析一下，最开始的时候数组的元素顺序是[0,1,0,3,12]

（1）当i=0时，不做移动，此时j=0

（2）当i=1时，将元素1，移动到j=0的位置，同时i=1位置的元素置0，此时数组元素顺序是[1,0,0,3,12]，然后j变为1

（3）当i=2时，不做移动，此时j=1

（4）当i=3时，将元素3，移动到j=1的位置，同时i=3位置的元素置0，此时数组元素的顺序是[1,3,0,0,12]，然后j变为2

（5）当i=4时，将元素12，移动到j=2的位置，同时i=4位置的元素置0，此时数组元素的顺序是[1,3,12,0,0]，然后j变为3

此种方法只对数组进行了一次遍历，时间复杂度为O(n)

盛最多水的容器

源自leetcode第11题

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

示例1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例2：
输入：height = [1,1]
输出：1

此题说简单点就是求一个矩形的面积最大值，矩形的长度就是数组中两个元素索引的差值，矩形的宽度就是两个元素的值中最小的那一个。主要的就是要确定数组中的两个元素。

最容易想到的方式就是两层循环遍历数组，然后依次求出来每两个元素组成的矩形的面积，然后找到最大值，但是这种方式不推荐，因为时间复杂度是O(n^2)

这里介绍一种可行的方案。就是收敛法，左右夹逼法。我们先确定矩形的长度（即x轴方向）为数组中的第一个和最后一个元素，这样最开始矩形的长度是最长的，高度待确定。然后我们让数组元素向数组中间收敛，如果说内部的元素的高度比外部元素高，并且计算的面积比外部元素面积也大，才进行矩形长度的变换，如果内部的元素高度比外部低，并且肯定长度也没有外部大，那替换就没有任何的意义。在收敛的过程中，直到数组中间停止，就能找到最大的面积以及对应的元素。这种方式只需要对数组遍历一次，所以时间复杂度是O(n)，代码如下

class Solution {
    public int maxArea(int[] height) {
        // 初始化矩形最大面积
        int max = 0;
        // 遍历数组，定义两个指针，一个是头元素，一个是尾元素，遍历条件就是两个指针保持头指针一定小于尾指针
        for (int i = 0, j = height.length - 1; i < j;) {
            // 先对确定矩形长度的两个元素对应的高度，取最小的那个，取完值后指针记得移动，头指针向后移动，尾指针向前移动
            int minHeight = height[i] < height[j] ? height[i++] : height[j--];
            // 计算矩形面积
            int area = (j - i + 1) * minHeight;
            // 记录最大面积
            max = Math.max(max, area);
        }
        return max;
    }
}

下面以数组[1,8,6,2,5,4,8,3,7]为例，进行步骤解析。

（1）最开始，i=0，j=8，满足i<j，数组的高度分别为1和7，取两者最小为1，然后变更i为1（左侧向内收敛），此时矩形的面积是(8-1+1)*1=8

（2）第二步，i=1，j=8，满足i<j，数组的高度分别为8和7，取两者最小为7，然后变更j为7（右侧向内收敛），此时矩形的面积是(7-1+1)*7=49

（3）第三步，i=1，j=7，满足i<j，数组的高度分别为8和3，取两者最小为3，然后变更j为6（右侧向内收敛），此时矩形的面积是(6-1+1)*3=18

（4）第四步，i=1，j=6，满足i<j，数组的高度分别为8和8，按逻辑取最小为8，然后变更j为5（右侧向内收敛），此时矩形的面积是(5-1+1)*8=40

（5）第五步，i=1，j=5，满足i<j，数组的高度分别为8和4，取最小值4，然后变更j为4（右侧向内收敛），此时矩形的面积是(4-1+1)*4=16

（6）第六步，i=1，j=4，满足i<j，数组的高度分别为8和5，取最小值5，然后变更j为3（右侧向内收敛），此时矩形的面积是(3-1+1)*5=15

（7）第七步，i=1，j=3，满足i<j，数组的高度分别是8和2，取最小值2，然后变更j为2（右侧向内收敛），此时矩形的面积是(2-1+1)*2=4

（8）第八步，i=1，j=2，满足i<j，数组的高度分别是8和6，取最小值6，然后变更j为1（右侧向内收敛），此时矩形的面积是(1-1+1)*6=6

（9）再往后，i=1，j=1，不满足i<j的条件，结束。那么最大的面积就是49.

爬楼梯

源自leetcode第70题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

此题的思路可以从简到繁的思考，假设只有一个台阶，那么只有一种走法就是一步，如果是2个台阶，那么可以2个一步，也可以一个2步。如果是三个台阶，一种方式是三个1步，第二种方式是先走一步，然后走1个2步，第三种方式是先走1个2步，然后再走1步。可以发现一个规律，如果我们上到第n个台阶，那么可以在第n-1个台阶处，直接走一步。也可以在第n-2个台阶处，直接走一个两步。同理，对于n-1个台阶，还有n-2个台阶，也是一样的，都可以在它们下面的一个台阶处走一步，或者在它们下面两个台阶处直接走1个两步。

所以可以得到下面的一个关系

1个台阶：1种

2个台阶：2种

3个台阶：f(1) + f(2) ，f(1)代表从第一个台阶直接跨2步，f(2)代表从第二个台阶直接跨1步。

。。。

n个台阶：f(n-2) + f(n-1) ，f(n-2)代表从第n-2个台阶上来的走法个数，f(n-1)代表从第n-1个台阶上来的走法个数。

很显然，这是一个逐层递归的过程，但是递归的缺点也很明显，它的时间复杂度是O(2^n)，效率很低。

因为我们最终要求的是最后一个台阶，也就是第n个台阶的走法，前面的所有台阶的走法，我们不关心，所以可以采用临时变量从前往后累加即可，下面还是从最简单的开始梳理

第一个台阶：1种走法(1)

第二个台阶：2种走法(1+1,2)

第三个台阶：是前两个台阶走法之和，为1+2=3

第四个台阶：是前两个台阶走法之和，为2+3=5

。。

这样就得到了下面的代码

class Solution {
    public int climbStairs(int n) {
        // 定义第一个台阶的步数
        int setp1 = 1;
        // 定义第二个台阶的步数
        int setp2 = 2;
        // 临时变量，用于统计前两个台阶的总步数
        int sum = 0;
        // 如果只有一个台阶，则直接返回定义的
        if (n == 1) {
            return setp1;
        }
        // 如果只有两个台阶，也是直接返回定义的
        if (n == 2) {
            return setp2;
        }
        // 从第三个台阶开始，循环进行前两个台阶总步数的累加，并更新临时变量
        for (int i = 3; i <= n; i++) {
            sum = setp1 + setp2;
            setp1 = setp2;
            setp2 = sum;
        }
        return sum;
    }
}

我们首先定义出来前两个最简单的，就是第一个台阶和第二个台阶的走法数量，并对输入的台阶数n做判断，如果是1或者2，那么就直接返回了。

然后下面来一个for循环，注意是从第三个台阶开始的，到第n个台阶结束。每次都是前两个台阶的走法数量之和，注意更新临时变量。这样，只对数组进行了一次遍历，时间复杂度是O(n)

三数之和

源自leetcode第15题

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

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

此题最容易想到的就是暴力求解，直接三层遍历，找三数之和为0的三个元素，但是时间复杂度太高，为O(n^3)，不推荐。

可以使用固定指针+双指针的形式来优化解决方案。有个前提，就是要先对整个数组进行排序，可以按照从小到大的顺序进行排列，选择的方式可以使用快排，时间复杂度为O(nlogn)

排序之后，从数组最左边开始，固定一个指针，该指针右边的剩余部分，在首和尾分别安排一个指针，它俩有条件的向中间进行移动，直到相遇。然后将那个固定指针右移一个位置，并且重新生成首尾指针，继续上面的步骤。下面通过图解的方式来体现出整个算法的思想。

假设开始数组是[-1,0,1,2,-1,-4]，经过排序之后的数组是[-4,-1,-1,0,1,2]

最开始，k在数组最左边索引为0处，i和j分别是数组剩余部分的首和尾，我们要找到arr[k] + arr[i] + arr[j] = 0的组合，也就是arr[i] + arr[j] = -arr[k]。比如现在，arr[k]是-4，那么我们要找到的arr[i] + arr[j] 要等于4才行，现在i和j的和才等于1，是小于4的，又因为我们的数组是已经按照从小到大的顺序排序好的，所以，要想等于4，是必须将i进行右移的（不能将j左移，否则i和j的和会比现在更小），那么就得到了下面的

这个时候的arr[i]的取值，和上面的arr[i]的取值是一样的，所以arr[i]和arr[j]的和与上次计算的一样。碰到这种情况，我们就直接跳过本次计算，将i继续右移。得到下面的

此时，arr[i]的值是0，arr[i] + arr[j]  = 2，2还是小于4的，所以应该继续将i进行右移。得到下面的

此时，arr[i]的值是1，arr[i] + arr[j] = 3，3还是小于4的，继续将i进行右移。得到下面的

此时，i和j进行了重叠，那么当arr[k] = -4时的本轮的计算就到此结束了。

接下来，应该将固定的指针进行右移，也就是k进行右移，得到arr[k] = -1，开始新一轮的计算，同时，i和j在新的一轮中，要重新进行归位（固定指针右侧的首和尾），最开始的状态如下

此时，arr[k]等于-1，我们要找到的 arr[i] + arr[j] 要等于1才行。当前的 arr[i] + arr[j] 正好等于1，那么就找到了一个组合[-1,-1,2]。找到组合之后，需要继续同时右移i和左移j，因为不确定后面是否还会有其他的组合结果，得到如下

此时arr[k]等于-1，arr[i] + arr[j] 刚好等于1，那么我们又找到了一个组合[-1,0,1]。接下来，需要继续右移i和左移j，但是移动之后，就不满足i < j 的条件了，因为两数是不允许重叠甚至交叉的。那么本轮就结束。

接下来，将固定的指针k继续右移，同时，重新归置i和j的位置，得到如下

此时会发现，arr[k] 的值和上一次的一样，都是-1，重复了，为了避免后续找到重复的组合，或者说上一次arr[k] 等于-1的所有i和j的组合都已经尝试过了，就直接跳过即可。继续右移固定指针k，同时重新归置i和j的位置，得到如下

此时arr[k]等于0，我们要找到 arr[i] + arr[j] 的和也等于0的情况。当前的 arr[i] + arr[j] 的和等于3，比0要大，此时应该要左移j，让它们的和减小，就得到了如下的

此时i和j发生了重叠，那么本轮就直接结束。

接下来继续右移固定指针k，得到如下的情况

我们先不去管i和j是否都还能有位置，单纯的看 arr[k] 的值，此时arr[k] 的值已经是1，大于0了，又因为数组是按照从小到大的顺序排列的，那么arr[i] + arr[j] 的值将永远大于0，永远也找不到符合条件的数据，本轮就可以直接结束了。

将上面的固定指针加双指针的思想，以及一些特殊情况条件的判断，落实到代码后，如下

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        // 先排序，按照从小到大的顺序
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        // 注意k的取值范围，从数组最开始，到数组倒数第三个元素(给i和j留出位置)
        for (int k = 0; k < nums.length - 2; k++) {
            // 如果nums[k]>0，则k之后的元素都大于0，则三数之和一定大于0，则退出循环
            if (nums[k] > 0) break;
            // 如果固定指针k右移之后的取值和上一次一样，说明有重复，则跳过
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            // 当固定指针k确定后，同时确定双指针i和j的最开始位置
            int i = k + 1;
            int j = nums.length - 1;
            // 双指针必须满足不能重叠
            while (i < j) {
                // 如果nums[i]+nums[j] < -nums[k],说明和太小，则右移i
                if (nums[i] + nums[j] < -nums[k]) {
                    // 跳过重复的i元素
                    while(i < j && nums[i] == nums[++i]);
                    // 如果nums[i]+nums[j] > -nums[k],说明和太大，则左移j
                } else if (nums[i] + nums[j] > -nums[k]){
                    // 跳过重复的j元素
                    while(i < j && nums[j] == nums[--j]);
                } else {
                    // 找到了三元组，添加到结果集中，并移动i和j
                    res.add(Arrays.asList(nums[k], nums[i], nums[j]));
                    // 跳过重复的i和j元素
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}

此算法的时间复杂度由两部分组成，一个是数组排序的，时间复杂度为O(nlogn)，另一个是由固定指针加双指针循环判断的。固定指针k是遍历了整个的数组，在k固定的情况下，指针i和j，也是遍历了数组剩余的部分，所以它的时间复杂度是O(n^2)，整体的时间复杂度按最高的来，最终就是O(n^2)，相比起暴力求解法，此方法算是一种优化了。