算法题解（数组篇）

谁借莪１个温暖的怀抱￠ 2022-09-15 14:53 140阅读 0赞

### 文章目录 ###

*   *  二分查找模板
     *  数组基础
     *  704. 二分查找 - 简单 - 10/13
     *  27. 移除元素 - 简单 - 10/13
     *  977. 有序数组的平方 - 简单 - 10/13
     *  209. 长度最小的子数组 - 中等 - 10/13
     *  59. 螺旋矩阵 II - 中等 - 10/13

## 二分查找模板 ##

l 指针掌管左边蓝色区域， r 指针掌管右边红色区域，两者互不冲突，通过不断向目标元素靠近扩大掌管区域，直到两者掌管区域接壤。

二分查找起始状态：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16]  
二分查找终止状态：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
＜ 、≤ 、≥ 、＞ 目标元素对应的蓝红区域划分  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
总结模板：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
例子：

class Solution { 
        public int[] searchRange(int[] nums, int target) { 
            //左边界
            int leftIdx = binarySearchLeft(nums, target); 
            //右边界
            int rightIdx = binarySearchRight(nums, target); 
            //判断是否符合
            if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {  
                return new int[]{ leftIdx, rightIdx};
            }
            return new int[]{ -1, -1};
        }
        
        //找左边界的二分查找
        public int binarySearchLeft(int[] nums, int target) { 
            //注意左右指针的初始值
            int left = -1, right = nums.length;
            while (left+1 != right) { 
                int mid = (left + right) / 2;
                if (nums[mid] >= target) { 
                    right = mid;
                } else { 
                    left = mid;
                }
            }
            return right;
        }
         //找右边界的二分查找
        public int binarySearchRight(int[] nums, int target) { 
            //注意左右指针的初始值
            int left = -1, right = nums.length;
            while (left+1 != right) { 
                int mid = (left + right) / 2;
                if (nums[mid] <= target) { 
                    left = mid;
                } else { 
                    right = mid;
                }
            }
            return left;
        }
    
    }

## 数组基础 ##

数组是存放在`连续内存空间`上的相同类型数据的集合。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
需要两点注意的是

*  数组下标都是从0开始的。
 *  数组内存空间的地址是连续的

正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

数组的元素是不能删的，`只能覆盖。`

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 5]

--------------------

## 704. 二分查找 - 简单 - 10/13 ##

[704. 二分查找 - 简单][704. _ -]

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 6]

class Solution { 
        public int search(int[] nums, int target) { 
            //注意左右指针的初始值
            int left = -1, right = nums.length;
            while (left+1 != right) { 
                int mid = (left + right) / 2;
                if (nums[mid] < target) { 
                    left = mid;
                } else { 
                    right = mid;
                }
            }
            //判断是否符合
            if (left < right && right < nums.length && nums[right] == target) {  
                return right;
            }
            return -1;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 7]

## 27. 移除元素 - 简单 - 10/13 ##

[27. 移除元素 - 简单][27. _ -]

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 8]![在这里插入图片描述][2f9c77db65924e7e96223e89abb79b69.png]

--------------------

解析：

双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

class Solution { 
        public int removeElement(int[] nums, int val) { 
            int slowIndex = 0; //慢指针
            for(int fastIndex=0; fastIndex<nums.length; fastIndex++){ 
                //如果还没找到val值，就快慢指针一起移动；
                if(nums[fastIndex] != val){ 
                    nums[slowIndex] = nums[fastIndex];
                    ++slowIndex;
                }
            }
            return slowIndex;
    
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 9]

## 977. 有序数组的平方 - 简单 - 10/13 ##

[977. 有序数组的平方 - 简单][977. _ -]

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 10]

--------------------

解析：

方法一：暴力排序，每个数平方之后，再排个序即可。

class Solution { 
        public int[] sortedSquares(int[] nums) { 
            int len = nums.length; //数组长度
            int[] result = new int[len]; //新数组
            for(int i=0; i<len; i++){ 
                result[i] = nums[i] * nums[i]; //每个数的平方
            }
            Arrays.sort(result); //排序
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 11]

--------------------

方法二：双指针

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A\[i\] \* A\[i\] < A\[j\] \* A\[j\] 那么result\[k–\] = A\[j\] \* A\[j\]; 。

如果A\[i\] \* A\[i\] >= A\[j\] \* A\[j\] 那么result\[k–\] = A\[i\] \* A\[i\]; 。

如下所示：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 12]

class Solution { 
        public int[] sortedSquares(int[] nums) { 
            int len = nums.length; //数组长度
            int[] result = new int[len]; //新数组
            int left = 0, right = len-1;
            int k = len-1; //新数组下标
            while(left <= right){ 
                //左右指针的值进行比较，大的就赋值入新数组，从末尾开始赋值，再移动左右指针
                if(nums[left] * nums[left] < nums[right] * nums[right]){ 
                    result[k--] = nums[right] * nums[right];
                    --right;
                }else{ 
                    result[k--] = nums[left] * nums[left];
                    ++left;
                }
            }
            return result;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 13]

## 209. 长度最小的子数组 - 中等 - 10/13 ##

[209. 长度最小的子数组 - 中等][209. _ -]

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 \[numsl, numsl+1, …, numsr-1, numsr\] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 14]  
![在这里插入图片描述][45c508b3fcb24fdca1765272d3d7516f.png]

--------------------

解析： 滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 15]

class Solution { 
        public int minSubArrayLen(int target, int[] nums) { 
            int left =0; // 滑动窗口起始位置
            int sum = 0; // 滑动窗口数值之和
            int result = Integer.MAX_VALUE; // 滑动窗口的长度
            for(int right=0; right<nums.length; right++){ 
                sum += nums[right];
                // 注意这里使用while，每次更新 left（起始位置），并不断比较子序列是否符合条件
                while(sum >= target){ 
                    result = Math.min(result, right-left+1);
                    sum = sum - nums[left]; // 这里体现出滑动窗口的精髓之处，不断变更left（子序列的起始位置）
                    ++left;
                }
            }
            // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
            return result == Integer.MAX_VALUE ? 0 : result;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 16]

## 59. 螺旋矩阵 II - 中等 - 10/13 ##

[59. 螺旋矩阵 II - 中等][59. _ II -]

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 17]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 18]

--------------------

解析：模拟过程，从左到右、从上到下、从右到左、从下到上填充。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 19]

class Solution { 
        public int[][] generateMatrix(int n) { 
            int left = 0, right = n-1, top = 0, bottom = n-1; //定义边界
            int[][] ans = new int[n][n];  //存放新数组
            int num = 1, end = n * n; //开始和结尾
            while(num <= end){ 
                for(int i=left; i<=right; i++) ans[top][i] = num++; //从左到右
                ++top;
                for(int i=top; i<=bottom; i++) ans[i][right] = num++; //从上到下
                --right;
                for(int i=right; i>=left; i--) ans[bottom][i] = num++; //从右到左
                --bottom;
                for(int i=bottom; i>=top; i--) ans[i][left] = num++; //从下到上
                ++left;                                    
            }
            return ans;
    
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 20]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fa557603b59f4c0ab83ee5b8ed93c175.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/75ec79c400ce4b21b7684ba70102baf5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/4cee0387979e41598e5facfde090260b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/bc52f5e397de4eb8b71fbd9af5380f2d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/40723e398594475488b7798f945322ea.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/f8ebcf848bb94975923e57b69916fc2c.png
[704. _ -]: https://leetcode-cn.com/problems/binary-search/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/c83fed81d4cd40c09ef04714c3800303.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/47cd74f3aa4d4bb9b5fe2f59ecba8e9b.png
[27. _ -]: https://leetcode-cn.com/problems/remove-element/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 8]: https://img-blog.csdnimg.cn/079071c1c74f497d966759d1d1866a49.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAeC1kcmFnb244ODk5,size_20,color_FFFFFF,t_70,g_se,x_16
[2f9c77db65924e7e96223e89abb79b69.png]: /images/20220828/59574273493241519d958f981de80ee2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/79e92742c51c407bb241a1d967201ec8.png
[977. _ -]: https://leetcode-cn.com/problems/squares-of-a-sorted-array/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220828/dfd98343ab3741148d08b7f24ed71388.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 11]: /images/20220828/ddf1763a9b3b43eea549bc0e9966de6b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 12]: /images/20220828/1e456e5375d040d9ae507f5101f27fed.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 13]: /images/20220828/13b1b544c0344a49ab12ee344b299ee1.png
[209. _ -]: https://leetcode-cn.com/problems/minimum-size-subarray-sum/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 14]: /images/20220828/f26578f9cd7642bf807c19668c188d1c.png
[45c508b3fcb24fdca1765272d3d7516f.png]: /images/20220828/01b18ef2dd0d49e6a80e72cfb31fea05.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 15]: /images/20220828/94482395deb8411692e6183e15e19697.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 16]: /images/20220828/da9e1cd1a83b494db31ecbc460e46cf9.png
[59. _ II -]: https://leetcode-cn.com/problems/spiral-matrix-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 17]: /images/20220828/767f0666cb0b4eada77be27554da6960.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 18]: /images/20220828/3113041faa7a4570ba4742f858078c82.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 19]: /images/20220828/ae27da760abe44daacdc168cd3eb6ec7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeC1kcmFnb244ODk5_size_20_color_FFFFFF_t_70_g_se_x_16 20]: /images/20220828/aaed52c2bf7a42a68f9e314c2b6f00bd.png