数组
数组的定义
数组是存放在连续内裤空间的相同类型数据的集合。
特点：
- 下标从0开始，通过下标可以获取元素，时间复杂度O(1)
- 存放相同类型的元素
- 内存空间的地址是连续的
- 每次移动指定位置元素需要移动其他元素的地址
- 数组元素不能删除，只能覆盖
一维数组：HashMap 的拉链寻址结构，ThreadLocal 的开放寻址结构
二维数组：部分算法中涉及
二分查找专题
二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4最简单的方式是使用for循环，找到目标值就停止，时间复杂度O(n)
需要设置左右指针，分别指向起始位置，然后找到中间元素，比中间元素小的都在左侧，比中间元素大的都在右侧，可以缩小一半范围。
需要注意循环的区间，
左闭右闭区间[left,right]
- 此时left==right，有意义
- 左右指针赋值的时候可以取中间元素的左右元素
在取中间值时候需要注意(left+right)/2，是存在问题的，假设left=Integer.MAX_VALUE,right=Integer.MAX_VALUE，left+right就会产生溢出，结果会变成一个负数（因为高位进位被截断），最终导致错误的结果。
public int search(int[] nums, int target) {
int left = 0 ;
int right = nums.length-1;
while(left<=right){
// 防止元素溢出
int mid = left +(right-left)/2;
if(nums[mid] < target){
left = mid+1;
}else if(nums[mid] > target){
right = mid -1;
}else{
return mid;
}
}
return -1;
}左闭右开区间[left,right)
- 此时不能使用left == right，因为取不到right位置元素
- 因为取不到right位置元素，所以右指针位置可以指向mid元素，而不是mid-1,而左指针因为是闭区间，可以取mid+1
public int search(int[] nums, int target) {
int left = 0 ;
int right = nums.length;
while(left<right){
int mid = left +(right-left)/2;
if(nums[mid] < target){
left = mid+1;
}else if(nums[mid] > target){
right = mid;
}else{
return mid;
}
}
return -1;
}- 时间复杂度：O(logn)，其中 n 是数组的长度。
- 空间复杂度：O(1)。
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2 public int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = left +(right-left)/2;
if(nums[mid] < target){
left = mid+1;
}else if(nums[mid] > target){
right = mid-1;
}else{
return mid;
}
}
// 查找不到这个元素
return right+1;
}在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]关键点：
- 非递减：递增
- 开始位置：左侧遍历第一个元素
- 结束位置：右侧遍历第一个元素
三种情况：
- target元素不在递增数组范围内，例如target=2, nums=[3,4,5], 返回[-1,-1]
- target元素在递增数组范围内，但是不在数组内，例如target=2, nums=[2,3,4], 返回[-1,-1]
- target元素在范围内，并且在数组内，返回下标
我们依然可以使用二分法遍历，但是当我们找到目标元素后，不是直接结束，而是需要进一步找到第一个元素位置，
- 寻找左边的第一个元素位置：当我们找到第一个符合元素，此时记录目标位置，但是这个位置并不一定是第一个元素位置，例如2，3，3，5，5，目标值设置为3，那么此时找到的第一个元素是位于下标2处，而不是第一个元素，所以我们需要记录当前位置，继续移动右指针，知道循环结束
- 寻找右边的第一个元素位置，和上面一样。
public int[] searchRange(int[] nums, int target) {
int left = getLeftBorder(nums, target);
int right = getRightBorder(nums, target);
if(left == -2 || right == -2){
return new int[]{-1,-1};
}
return new int[] { left, right };
}
// 寻找左边的边界
public int getLeftBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// 记录左边界
int leftBorder = -2;
while (left <= right) {
int mid = left + ((right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if(nums[mid] > target) {
right = mid - 1;
}else{
// 需要继续移动right指针，找到第一个target位置
right = mid -1;
leftBorder = mid;
}
}
return leftBorder;
}
// 寻找右边的边界
public int getRightBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// 记录左边界
int rightBorder = -2;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] < target){
left = mid + 1;
}else{
// 需要继续移动left指针，找到最后一个target位置
left = mid+1;
rightBorder = mid;
}
}
return rightBorder;
}时间复杂度：O(logn)
但是我们会发现，以上的代码比较冗余，可以左右边界统一处理，例如2，3，3，4，5，目标值设置为3，我们第一次二分遍历即可找到当前目标元素的位置，而一定是有重复的数据，要么在左，要么在右，我们可以在这个范围内查找元素。
public int[] searchRange(int[] nums, int target) {
// 1. 二分遍历里面招不到指定元素
int index = binarySearch(nums, target);
if (index == -1) {
return new int[] { -1, -1 };
}
// 2. 左边界第一个元素
int left = index;
while (left - 1 >= 0 && nums[left - 1] == target) {
left--;
}
// 3. 右边界第一个元素
int right = index;
while (right + 1 <= nums.length && nums[right + 1] == target) {
right++;
}
return new int[] { left, right };
}
/**
* 二分查找
*/
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) / 2);
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
return mid;
}
}
return -1;
}x的平方
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
输入：x = 4
输出：2示例 2：
输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。二分查找
x 平方根的整数部分 ans 是满足 k^2≤x ,我们只需要对k进行二分查找，上限可以设置为x，下限可以设置为0，区间范围[0,x]，只需要使用mid*mid <= x，即可找到目标值。但是需要注意mid × mid可能会超过int范围，需要使用long处理。
public int mySqrt(int x) {
int left = 0;
int right = x;
int result = 1;
while(left <=right){
int mid = left +(right-left)/2;
if((long)mid*mid <= x){
left = mid+1;
result = mid;
}else{
right = mid-1;
}
}
return result;
}有效数字的平方
给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数，如 sqrt 。
示例 1：
输入：num = 16
输出：true
解释：返回 true ，因为 4 * 4 = 16 且 4 是一个整数。二分法，这题和上面一题一样
public boolean isPerfectSquare(int num) {
int left = 0;
int right = num;
while(left <= right){
int mid = left +(right-left)/2;
long res = (long) mid*mid;
if(res == num){
return true;
}else if(res < num){
left = mid+1;
}else{
right = mid-1;
}
}
return false;
}这两题还有一个牛顿迭代法
https://leetcode.cn/problems/sqrtx/solutions/238553/x-de-ping-fang-gen-by-leetcode-solution/
总结
二分查找简单，需要确定号两个是闭区间，还是左闭右开，然后灵活的根据题目条件确定循环范围。
双指针专题
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
- 更改
nums数组，使nums的前k个元素包含不等于val的元素。nums的其余元素和nums的大小并不重要。 - 返回
k
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]双指针
从题目可知，我们只需要返回前k个不包含元素的个数，我们只需要设置两个指针，分别从起始位置移动，如果左指针遇到目标值，那么就和右指针进行交换，直到左右指针相遇，那么就保证，左指针左侧的元素一定不是目标元素，我们直接返回左指针位置。
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
if (nums[left] == val) {
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
--right;
} else {
{
left++;
}
}
}
return left;
}- 时间复杂度：O(n)，其中 n 为序列的长度。我们只需要遍历该序列至多一次。
- 空间复杂度：O(1)。我们只需要常数的空间保存若干变量。
快慢双指针
我们可以设置快慢指针，区别于上面的双指针，这两个指针是从同一个起点出发，快指针先走，如果快指针的值不等于目标值，那么此时慢指针就往后移动指向当前的快指针的值。
public int removeElement(int[] nums, int val) {
int slowIndex = 0;
for(int fastIndex = 0; fastIndex<nums.length;fastIndex++){
if(nums[fastIndex] != val){
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}删除有序数组中的重复项
给你一个 非严格递增排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
- 更改数组
nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]快慢双指针
和上面一样，我们可以设置两个指针，当快指针移动的时候，需要判断当前快指针元素是否等于慢指针元素，如果等于，说明重复，那么快指针移动，不进行慢指针移动，当两者不等于，此时才会移动慢指针到快指针位置。
public int removeDuplicates(int[] nums) {
int length = nums.length;
if(length == 0 || length == 1){
return length ;
}
int slow = 0;
for(int fast = 0;fast<length;fast++){
if(nums[fast] != nums[slow]){
// 先移动指针，然后赋值
nums[++slow] = nums[fast];
}
}
return slow+1;
}- 时间复杂度：O(n)，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。
- 空间复杂度：O(1)。只需要使用常数的额外空间。
这道题有个非常需要注意的问题，那就是我们要先移动slow指针，然后赋值到slow+1指针位置，因为我们需要保留第一个元素，如果直接使用slow++，会先将当前的值赋给slow，然后slow才自增。
{1,1,2}为例，当fast指针到达元素2的位置时候，此时slow还是0，这时候会将num[fast]赋值给nums[slow]，也就变成了nums = {2, 1, 2}，而我们需要的是{1,2,2}，很明显slow++是有问题的。
移动0
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]简单思路，遇到0直接进行交换。
还可以使用两个快慢指针，当快指针遇到不是0的元素，慢指针指向当前元素，当快指针访问完所有的元素后，此时慢指针指向的位置左侧全是排列好的非0元素，右侧剩余部分元素，直接赋值为0，即可实现上述需求。
public void moveZeroes(int[] nums) {
int slow = 0;
int fast = 0;
// 使用slow指针关联不是0的数据
while(fast<nums.length){
if(nums[fast] != 0 ){
nums[slow++] = nums[fast];
}
fast++;
}
// slow已经找到所有不是0的数据，后面元素全部归0即可
for(int i = slow;i<nums.length;i++){
nums[i] = 0;
}
}有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
- 请你设计时间复杂度为
O(n)的算法解决本问题
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]最简单的方法是先平方，然后使用Arrays.sort()进行数组排序，而Arrays的排序是使用快排，时间复杂度O(nlogn)。
我们可以发现平方后的元素最大值要么在左边，要么在右侧，我们只需要比较左侧和右侧的元素平方，将最大的元素逆序写入数组，这样只需要遍历一次数组。
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
int left = 0;
int right = nums.length - 1;
int index = nums.length - 1;
while (left <= right) {
// 左指针位置元素大
if (nums[left] * nums[left] >= nums[right] * nums[right]) {
res[index] = nums[left] * nums[left];
left++;
}else{
// 右指针位置元素大
res[index] = nums[right] * nums[right];
right--;
}
index --;
}
return res;
}总结
对于移除元素我们可以使用双指针
- 左右指针
- 快慢指针
滑动窗口专题
长度最小子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。暴力法
我们需使用两次循环，第一次循环为了控制遍历次数，第二次遍历是为了获取当前循环中的最小子数组长度。一次流程如下，我们只需要计算每次循环下最小长度，然后比较。
public int minSubArrayLen(int target, int[] nums) {
int res =Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
int sum =0;
for(int j=i;j<nums.length;j++){
sum += nums[j];
if(sum >= target){
res= Math.min(res,j-i+1);
break;
}
}
}
return res == Integer.MAX_VALUE ? 0 :res;
}时间复杂度：O(n*n)
滑动窗口
可以设置两个指针，left和right，可以看作一个窗口，right负责右移，当左右范围的和大于等于目标值，此时记录最小值，将左元素移除，继续寻找最小值。
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，核心要素如下：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
public int minSubArrayLen(int target, int[] nums) {
int res =Integer.MAX_VALUE;
int left = 0;
int sum =0;
for(int right =0;right<nums.length;right++){
sum += nums[right];
while(sum >=target){
res = Math.min(res,right-left+1);
sum -= nums[left++];
}
}
return res == Integer.MAX_VALUE ? 0:res;
}时间复杂度：O(n)
空间复杂度：O(1)
不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)
贡献者
flycodeu
版权所有
版权归属：