java数组里不是字母的函数_Java/1_数组问题.md at master · a928755613/Java · GitHub

深藏阁楼爱情的钟 2022-11-08 14:18 13阅读 0赞

数组问题

一、数组基础

1、移动零(283)

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: \[0,1,0,3,12\]

输出: \[1,3,12,0,0\]

说明:

必须在原数组上操作，不能拷贝额外的数组。

尽量减少操作次数。

//思路一：

//1、引入另外一个指针k,用于指向数组中非0元素(原有一个遍历数组的指针i)，很显然k <= nums.length-1

//2、\[0,k)中元素是非0元素，i指向非0元素，就与k指向的元素交换，这样保证元素的相对顺序

public void moveZeroes(int\[\] nums) \{

int k = 0;

for(int i=0;i

if(nums\[i\]!=0)\{

swap(nums,k++,i);

private void swap(int\[\] nums,int i,int j)\{

int tmp = nums\[i\];

nums\[i\] = nums \[j\];

nums\[j\] = tmp;

//思路二：是对思路一的改进

public void moveZeroes(int\[\] nums) \{

int k = 0;

for(int i=0;i

if(nums\[i\]!=0)\{

if(i != k)\{

swap(nums,k++,i);

\}else\{

k++;

private void swap(int\[\] nums,int i,int j)\{

int tmp = nums\[i\];

nums\[i\] = nums \[j\];

nums\[j\] = tmp;

2、最大连续1的个数(485)

给定一个二进制数组， 计算其中最大连续1的个数。

示例 1:

输入: \[1,1,0,1,1,1\]

输出: 3

解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是 3.

注意：

输入的数组只包含 0 和1。

输入数组的长度是正整数，且不超过 10,000。

public int findMaxConsecutiveOnes(int\[\] nums) \{

int res = 0;

int count = 0; //计算连续 1 的个数

for(int num : nums)\{

if(num == 0)\{

count = 0 ; //count 重新计算

\}else\{

count++;

res = Math.max(res,count);

return res;

3、错误的集合(645)

集合 S 包含从1到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个元素复制了成了集合里面的另外一个元素的值，导致集合丢失了一个整数并且有一个元素重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。你的任务是首先寻找到重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1:

输入: nums = \[1,2,2,4\]

输出: \[2,3\]

注意:

给定数组的长度范围是 \[2, 10000\]。

给定的数组是无序的。

//思路一：空间换时间的思路

public int\[\] findErrorNums(int\[\] nums) \{

int\[\] freq = new int\[nums.length+1\];

for (int num : nums)\{

freq\[num\]++;

int res1 = 0,res2=0;

for(int num=1;num<=nums.length;num++)\{

if(freq\[num\] == 2)\{

res1 = num;

if(freq\[num\] == 0)\{

res2 = num;

return new int\[\]\{res1,res2\};

//思路二：最直接的方法是先对数组进行排序，这种方法时间复杂度为 O(NlogN)。

//本题可以以 O(N) 的时间复杂度、O(1) 空间复杂度来求解。

//主要思想是通过交换数组元素，使得数组上的元素在正确的位置上。

public int\[\] findErrorNums(int\[\] nums) \{

for (int i = 0; i < nums.length; i++) \{

while (nums\[i\] != i + 1 && nums\[nums\[i\] - 1\] != nums\[i\]) \{

swap(nums, i, nums\[i\] - 1);

for (int i = 0; i < nums.length; i++) \{

if (nums\[i\] != i + 1) \{

return new int\[\]\{nums\[i\], i + 1\};

return null;

private void swap(int\[\] nums, int i, int j) \{

int tmp = nums\[i\];

nums\[i\] = nums\[j\];

nums\[j\] = tmp;

\*4、找到所有数组中消失的数字(448)

给定一个范围在 1 ≤ a\[i\] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 \[1, n\] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为\*O(n)\*的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

输入:

\[4,3,2,7,8,2,3,1\]

输出:

\[5,6\]

//思路：通过交换数组元素，使得数组上的元素在正确的位置上。

public List findDisappearedNumbers(int\[\] nums) \{

List res = new ArrayList<>();

if(nums== null || nums.length==0)\{

return res;

for(int i=0;i

if(nums\[i\] != nums\[nums\[i\]-1\])\{

swap(nums,i,nums\[i\]-1);

i--;

//System.out.println(Arrays.toString(nums));

for(int i=0;i

if(nums\[i\] != i+1)\{

res.add(i+1);

return res;

private void swap(int\[\] nums,int i,int j)\{

int tmp = nums\[i\];

nums\[i\] = nums\[j\];

nums\[j\] = tmp;

5、数组中重复的数据(442)

给定一个整数数组 a，其中1 ≤ a\[i\] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

输入:

\[4,3,2,7,8,2,3,1\]

输出:

\[2,3\]

public List findDuplicates(int\[\] nums) \{

List res = new ArrayList<>();

for(int i=0;i

if(nums\[i\] != nums\[nums\[i\]-1\])\{

swap(nums,i,nums\[i\]-1);

i--;

// 与 448 题不同之处

for(int i=0;i

if(nums\[i\] !=i+1)\{

res.add(nums\[i\]);

return res;

private void swap(int\[\] nums,int i,int j)\{

int tmp = nums\[i\];

nums\[i\] = nums\[j\];

nums\[j\] = tmp;

\*6、 寻找重复数(287)

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间(包括 1 和 n)，可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: \[1,3,4,2,2\]

输出: 2

示例 2:

输入: \[3,1,3,4,2\]

输出: 3

说明：

不能更改原数组(假设数组是只读的)。

只能使用额外的 O(1) 的空间。

时间复杂度小于 O(n2) 。

数组中只有一个重复的数字，但它可能不止重复出现一次。

//思路一：二分查找解法

public int findDuplicate(int\[\] nums) \{

int l = 1, h = nums.length - 1;

while (l <= h) \{

int mid = l + (h - l) / 2;

int cnt = 0;

for (int i = 0; i < nums.length; i++) \{

if (nums\[i\] <= mid) cnt++;

if (cnt > mid) h = mid - 1;

else l = mid + 1;

return l;

//思路二：双指针解法，类似于有环链表中找出环的入口

//参考 141 、142

//思路：注意说明里面的要求

public int findDuplicate(int\[\] nums) \{

// nums 的长度是(n+1),元素的范围在\[1,n\]之间

int slow = nums\[0\];

int fast = nums\[0\];

while(true)\{

slow = nums\[slow\];

fast = nums\[nums\[fast\]\];

if(slow == fast)\{

break;

slow = nums\[0\];

while(slow != fast)\{

slow = nums\[slow\];

fast = nums\[fast\];

return slow;

7、数组的度(697)

给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1:

输入: \[1, 2, 2, 3, 1\]

输出: 2

解释:

输入数组的度是2，因为元素1和2的出现频数最大，均为2.

连续子数组里面拥有相同度的有如下所示:

\[1, 2, 2, 3, 1\], \[1, 2, 2, 3\], \[2, 2, 3, 1\], \[1, 2, 2\], \[2, 2, 3\], \[2, 2\]

最短连续子数组\[2, 2\]的长度为2，所以返回2.

示例 2:

输入: \[1,2,2,3,1,4,2\]

输出: 6

注意:

nums.length 在1到50,000区间范围内。

nums\[i\] 是一个在0到49,999范围内的整数。

public int findShortestSubArray(int\[\] nums) \{

//统计 nums 中数字出现的次数

HashMap freq = new HashMap<>();

HashMap numLastIndex = new HashMap<>();

HashMap numFirstIndex = new HashMap<>();

for(int i=0;i

int num = nums\[i\];

freq.put(num,freq.getOrDefault(num,0)+1);

numLastIndex.put(num,i);

if(!numFirstIndex.containsKey(num))\{

//判断是否已经存在 num,如果已经存在，就不能覆盖，因为这是该元素在数组中的起始下标

numFirstIndex.put(num,i);

//获取该数组的度

int degree = 0;

for(int num : nums)\{

degree = Math.max(degree,freq.get(num));

int res = Integer.MAX\_VALUE;

//要保证最短，则该连续子数组值需从 num 的开始位置和结束位置截取

for(int num : nums)\{

if(freq.get(num) < degree)\{

continue;

res = Math.min(res,numLastIndex.get(num)-numFirstIndex.get(num)+1);

return res;

8、优美的排列II(667)

给定两个整数 n 和 k，你需要实现一个数组，这个数组包含从 1 到 n 的 n 个不同整数，同时满足以下条件：

① 如果这个数组是 \[a1, a2, a3, ... , an\] ，那么数组 \[|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|\] 中应该有且仅有 k 个不同整数；.

② 如果存在多种答案，你只需实现并返回其中任意一种.

示例 1:

输入: n = 3, k = 1

输出: \[1, 2, 3\]

解释: \[1, 2, 3\] 包含 3 个范围在 1-3 的不同整数， 并且 \[1, 1\] 中有且仅有 1 个不同整数 : 1

示例 2:

输入: n = 3, k = 2

输出: \[1, 3, 2\]

解释: \[1, 3, 2\] 包含 3 个范围在 1-3 的不同整数， 并且 \[2, 1\] 中有且仅有 2 个不同整数: 1 和 2

提示:

n 和 k 满足条件 1 <= k < n <= 104.

让前 k+1 个元素构建出 k 个不相同的差值，序列为：1 k+1 2 k 3 k-1 ... k/2 k/2+1.

public int\[\] constructArray(int n, int k) \{

int\[\] ret = new int\[n\];

ret\[0\] = 1;

for (int i = 1, interval = k; i <= k; i++, interval--) \{

ret\[i\] = i % 2 == 1 ? ret\[i - 1\] + interval : ret\[i - 1\] - interval;

for (int i = k + 1; i < n; i++) \{

ret\[i\] = i + 1;

return ret;

9、嵌套数组(565)

Input: A = \[5,4,0,3,1,6,2\]

Output: 4

Explanation:

A\[0\] = 5, A\[1\] = 4, A\[2\] = 0, A\[3\] = 3, A\[4\] = 1, A\[5\] = 6, A\[6\] = 2.

One of the longest S\[K\]:

S\[0\] = \{A\[0\], A\[5\], A\[6\], A\[2\]\} = \{5, 6, 2, 0\}

题目描述：S\[i\] 表示一个集合，集合的第一个元素是 A\[i\]，第二个元素是 A\[A\[i\]\]，如此嵌套下去。求最大的 S\[i\]。

public int arrayNesting(int\[\] nums) \{

int max = 0;

for (int i = 0; i < nums.length; i++) \{

int cnt = 0;

for (int j = i; nums\[j\] != -1; ) \{

cnt++;

int t = nums\[j\];

nums\[j\] = -1; // 标记该位置已经被访问

j = t;

max = Math.max(max, cnt);

return max;

10、最多能完成排序的块(769)

数组arr是\[0, 1, ..., arr.length - 1\]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。

我们最多能将数组分成多少块？

示例 1:

输入: arr = \[4,3,2,1,0\]

输出: 1

解释:

将数组分成2块或者更多块，都无法得到所需的结果。

例如，分成 \[4, 3\], \[2, 1, 0\] 的结果是 \[3, 4, 0, 1, 2\]，这不是有序的数组。

示例 2:

输入: arr = \[1,0,2,3,4\]

输出: 4

解释:

我们可以把它分成两块，例如 \[1, 0\], \[2, 3, 4\]。

然而，分成 \[1, 0\], \[2\], \[3\], \[4\] 可以得到最多的块数。

注意:

arr 的长度在 \[1, 10\] 之间。

arr\[i\]是 \[0, 1, ..., arr.length - 1\]的一种排列。

题目描述：分隔数组，使得对每部分排序后数组就为有序。

public int maxChunksToSorted(int\[\] arr) \{

if (arr == null) return 0;

int ret = 0;

int right = arr\[0\];

for (int i = 0; i < arr.length; i++) \{

right = Math.max(right, arr\[i\]);

if (right == i) ret++;

return ret;

二、二分查找

1、二分查找(704)

问题描述：给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ，

写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = \[-1,0,3,5,9,12\], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = \[-1,0,3,5,9,12\], target = 2

输出: -1

解释: 2 不存在 nums 中因此返回 -1

//思路：典型的二分查找

//写法一：在区间 \[l,r\]中查找target元素

public int search(int\[\] nums, int target) \{

int l = 0;

int r = nums.length -1;

while(l<=r)\{

int mid = (r-l)/2 + l;

if(nums\[mid\]==target)\{

return mid;

\}else if(nums\[mid\]>target)\{

r = mid-1;

\}else\{

l = mid+1;

return -1;

//写法二：在区间 \[l,r)中查找target元素

public int search(int\[\] nums, int target) \{

int l = 0;

int r = nums.length;

while(l

int mid = (r-l)/2 + l;

if(nums\[mid\]==target)\{

return mid;

\}else if(nums\[mid\]>target)\{

r = mid;

\}else\{

l = mid+1;

return -1;

2、第一个错误版本(278)

问题描述：你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 \[1, 2, ..., n\]，你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。

实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false

调用 isBadVersion(5) -> true

调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

/\* The isBadVersion API is defined in the parent class VersionControl.

boolean isBadVersion(int version); \*/

public class Solution extends VersionControl \{

//思路：

//如果第 m 个版本出错(即 isisBadVersion(mid) == true)，

//则表示第一个错误的版本在 \[l, m\] 之间，令 r = m ；

//否则第一个错误的版本在 \[m + 1, h\] 之间，令 l = m + 1。

//注意:这里判断条件 l < r

public int firstBadVersion(int n) \{

int l = 1;

int r = n;

while(l

int mid = (r-l)/2+l;

if(isBadVersion(mid))\{

r = mid;

\}else\{

l = mid+1;

return l;

3、x 的平方根(69)

问题描述：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4

输出: 2

示例 2:

输入: 8

输出: 2

说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

//思路：典型的利用二分查找

//\[l,r\]中查找值为 sqrt 的元素。

//同时 sqrt 的值和l、r 有关，而l，r 是不断变化的

class Solution \{

public int mySqrt(int x) \{

if(x<=1)\{

return x;

int l = 0;

int r = x;

while(l<=r)\{

int mid = (r-l)/2 + l;

int sqrt = x/mid;

if(sqrt == mid)\{

return mid;

\}else if(sqrt > mid)\{

l = mid + 1;

\}else\{

assert sqrt < mid;

r = mid - 1;

//循环结束时 l > r,这里忽略小数部分。

return r;

4、寻找旋转排序数组中的最小值(153)

问题描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。请找出其中最小的元素。

示例 1:

输入: \[3,4,5,1,2\]

输出: 1

示例 2:

输入: \[4,5,6,7,0,1,2\]

输出: 0

/\*\*

\* 思路：

\* 第一个小于前一个元素的元素，就是最小值。

\* 我们通过二分查找的，进行优化。

\*/

class Solution \{

public int findMin(int\[\] nums) \{

if(nums.length == 1)\{

return nums\[0\];

if(nums.length == 2)\{

return Math.min(nums\[0\],nums\[1\]);

int l = 0;

int h = nums.length -1;

while(l<=h)\{

if(l==h)\{

return nums\[l\];

int mid = (h-l)/2 + l;

if(nums\[mid\] > nums\[mid+1\])\{

return nums\[mid+1\];

if(nums\[mid\] < nums\[h\])\{

h = mid;

\}else if(nums\[mid\] > nums\[h\])\{

l = mid;

return nums\[l\];

5、搜索旋转排序数组(33)

问题描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = \[4,5,6,7,0,1,2\], target = 0

输出: 4

示例 2:

输入: nums = \[4,5,6,7,0,1,2\], target = 3

输出: -1

//思路：非常重要的性质，对于数组nums \[0,1,2,3,4,5,6,7\],有7种旋转方法，包括原来的数组

//\[0 1 2 \{3\} 4 5 6 7\]

//\[1 2 3 \{4\} 5 6 7 0\]

//\[2 3 4 \{5\} 6 7 0 1\]

//\[3 4 5 \{6\} 7 0 1 2\]

//\[5 6 7 \{0\} 1 2 3 4\]

//\[6 7 0 \{1\} 2 3 4 5\]

//\[7 0 1 \{2\} 3 4 5 6\]

//可以看出

//当 nums\[mid\] > nums\[r\] 时，左半部分是有序的,可以使用二分查找

//当 nums\[mid\] < nums\[r\] 时，右半部分是有序的,可以使用二分查找

class Solution \{

public int search(int\[\] nums, int target) \{

int l = 0;

int r = nums.length -1;

while(l<=r)\{

int mid = l + (r-l)/2;

if(nums\[mid\] == target)\{

return mid;

\}else if(nums\[mid\] > nums\[r\])\{ //左半部分\[l,mid-1\]是有序的。

if(target >= nums\[l\] && target < nums\[mid\])\{ //判断target是否在\[l,mid-1\]

r = mid - 1;

\}else\{

l = mid + 1;

\}else\{ //右半部分\[mid+1,r\]是有序的。

if(target > nums\[mid\] && target <= nums\[r\])\{ //判断target是否在\[mid+1,,r\]

l = mid + 1;

\}else\{

r = mid - 1;

return -1;

6、在排序数组中查找元素的第一个和最后一个位置(34)

问题描述：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 \[-1, -1\]。

示例 1：

输入: nums = \[5,7,7,8,8,10\], target = 8

输出: \[3,4\]

示例 2:

输入: nums = \[5,7,7,8,8,10\], target = 6

输出: \[-1,-1\]

class Solution \{

public int\[\] searchRange(int\[\] nums, int target) \{

int first = binarySearchFirstTarget(nums,target);

int last = binarySearchLastTarget(nums,target);

return new int\[\]\{first,last\};

//查找第一个target元素的下标

private int binarySearchFirstTarget(int\[\] nums,int target)\{

int l = 0;

int r = nums.length-1;

int res = -1;

while(l<=r)\{

int mid = l + (r-l)/2;

if( target <= nums\[mid\])\{

r = mid -1;

\}else\{

l = mid + 1;

if(target == nums\[mid\])\{

res = mid;

return res;

//查找最后一个target元素的小标

private int binarySearchLastTarget(int\[\] nums,int target)\{

int l = 0;

int r = nums.length-1;

int res = -1;

while(l<=r)\{

int mid = l + (r-l)/2;

/\*if( target <= nums\[mid\])\{

r = mid -1;

\}else\{

l = mid + 1;

\}\*/

if(target >= nums\[mid\])\{

l = mid + 1;

\}else\{

r = mid - 1;

if(target == nums\[mid\])\{

res = mid;

return res;

7、爱吃香蕉的珂珂(875)

问题描述：珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles\[i\] 根香蕉。警卫已经离开了，将在 H 小时后回来。珂珂可以决定她吃香蕉的速度 K (单位：根/小时)。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。

如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。

示例 1：

输入: piles = \[3,6,7,11\], H = 8

输出: 4

示例 2：

输入: piles = \[30,11,23,4,20\], H = 5

输出: 30

示例 3：

输入: piles = \[30,11,23,4,20\], H = 6

输出: 23

// 思路：珂珂吃香蕉的最快速度就是 N 个堆中香蕉数目最多的堆中的数目。

// 可以在 H 小时内吃掉所有香蕉的最小速度 K。就是求他在警卫刚好回来的时候，刚好吃完所有的香蕉。

class Solution \{

public int minEatingSpeed(int\[\] piles, int H) \{

if (piles.length > H ) \{

return -1;

//maxSpeed KOKO吃香蕉的最快速度

int maxSpeed=piles\[0\];

for(int i=0;i

maxSpeed=Math.max(maxSpeed,piles\[i\]);

//KOKO吃香蕉的速度在\[1,maxSpeed\]之间

int l=1;

int h=maxSpeed;

while(l<=h)\{

int mid=l+(h-l)/2;

int hours=hours(piles,mid);

if(hours==H)\{

return mid;

\}else if(hours

//hours

h=mid-1;

\}else\{

//hours>H说明吃的慢了，速度要快起来

l=mid+1;

return l;

//以spped速度吃香蕉所花费的时间

private int hours(int\[\] piles,int speed)\{

int time=0;

for(int pile:piles)\{

time += Math.ceil(pile\*1.0/speed);

return time;

8、有序数组中的单一元素(540)

问题描述：给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: \[1,1,2,3,3,4,4,8,8\]

输出: 2

示例 2:

输入: \[3,3,7,7,10,11,11\]

输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

//思路： index 为 Single Element 在数组中的位置。

//如果 m 为偶数，

//m + 1 < index，那么 nums\[m\] == nums\[m + 1\]；

//m + 1 >= index，那么 nums\[m\] != nums\[m + 1\]。

//从上面的规律可以知道，

//如果 nums\[m\] == nums\[m + 1\]，那么 index 所在的数组位置为 \[m + 2, h\]，此时令 l = m + 2；

//如果 nums\[m\] != nums\[m + 1\]，那么 index 所在的数组位置为 \[l, m\]，此时令 h = m。

//注意循环条件 l < r

public int singleNonDuplicate(int\[\] nums) \{

int l = 0;

int h = nums.length - 1;

while(l

int m = (h-l)/2+l;

if(m%2==1)\{ //始终保持 m 是偶数

m--;

if(nums\[m\] == nums\[m+1\])\{

l = m+2;

\}else\{

h = m;

return nums\[l\];

9、寻找两个有序数组的中位数(4)

问题描述：给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = \[1, 3\]

nums2 = \[2\]

则中位数是 2.0

示例 2:

nums1 = \[1, 2\]

nums2 = \[3, 4\]

则中位数是 (2 + 3)/2 = 2.5

//思路一：直接合并然后求解，但是不合题意。

//时间复杂度：O(m+n)

//空间复杂度：O(m+n)

public double findMedianSortedArrays(int\[\] nums1, int\[\] nums2) \{

int len = nums1.length + nums2.length;

int\[\] nums = new int\[len\];

int index = 0;

int i = 0;

int j = 0;

while(i

if(nums1\[i\] < nums2\[j\])\{

nums\[index++\] = nums1\[i++\];

\}else\{

nums\[index++\] = nums2\[j++\];

while(i< nums1.length)\{

nums\[index++\] = nums1\[i++\];

while(j< nums2.length)\{

nums\[index++\] = nums2\[j++\];

if(len % 2 ==1)\{

return nums\[nums.length/2\]\*1.0;

\}else\{

return (nums\[nums.length/2\] + nums\[nums.length/2-1\])\*1.0 / 2;

//思路二：

//1、要求时间复杂度 O(log(m+n)),m+n就是两个数组的长度和，又是有序数组，我们很容易想到二分查找

//2、求出的结果是中位数，中位数的特点是其以后的数都比它大，前面的数都比它小。

//3、两个数组都已经是有序数组，

// 因此我们所需要的结果就是num1\[start1,end1\]中的第i个元素(下标 start1+i-1)和数组num2\[start2,end2\]中第j个元素(下标 start+j-1)，

///在数组num1\[start1,end1\]中确定i以及在数组中确定num2\[start2,end2\]，此时可以采用二分查找的方法，

// 通过不断缩小查找范围来确实所需要查找的值，也符合题目中所要求的分治算法的思想。

public double findMedianSortedArrays(int\[\] nums1, int\[\] nums2) \{

int len1 = nums1.length;

int len2 = nums2.length;

int k1 = (len1+len2+1)/2;

int k2 = (len1+len2+2)/2;

//当 (len1+len2)奇数时，此时 k1==k2;

//当 (len1+len2)偶数时，此时 k1+1 == k2

double res =

(findKth(nums1,0,len1-1,nums2,0,len2-1,k1) +

findKth(nums1,0,len1-1,nums2,0,len2-1,k2))/2;

return res;

/\*\*

\* 查找 nums1\[start1,end1\] 和 nums2\[start2,end2\]合并后的第 k 小元素

\*/

private double findKth(int\[\] nums1, int start1, int end1, int\[\] nums2, int start2, int end2, int k) \{

//计算当前数组范围内的数组长度

int len1 = end1 - start1 + 1;

int len2 = end2 - start2 + 1;

if(len1 > len2)\{

//这里保持 len1 <= len2,方便后面的操作

return findKth(nums2,start2,end2,nums1,start1,end1,k);

\}else if(len1 == 0)\{

//nums1\[start1,start2\]数组长度为0，则就是在nums2\[start2,end2\]中第 k 小的元素

return nums2\[start2+k-1\];

\}else if(k == 1)\{

//合并后的数组的第1个元素，显然是nums1\[start1,end1\]和nums2\[start2,end2\]中第一个元素的较小值

return Math.min(nums1\[start1\],nums2\[start2\]);

//分治

int i = Math.min(k/2,len1); //在nums1\[start1,end1\]中第 i 小元素

int j = k - i; //在nums2\[start2,end2\]中第 j 小元素

if(nums1\[start1+i-1\] > nums2\[start2+j-1\])\{ //此时 nums2\[start2,end2\]中就要舍弃前面j个元素

/\*\*

\* 使用反证法证明：

\* 证：当k/2 >= len1 时，而我们要找的k就在nums2\[start2,end2\]的前 k/2元素中。

\* 我们假设 k 所在的数组下标记为p，那么nums2\[start2,end2\]中含有的属于后数组前k个元素的元素有(p+1)个。

\* 显然，nums1\[start1,end1\]中必然含有另外 k-(p+1)个元素。

\* 由此，得到如下不等式：

\* p <= k/2 - 1 (k th 实际所处位置为p，在nums2\[start2,end2\]的前k/2个元素里。-1是因为现在算的是数组下标，从0开始)

\* ==> p + 1 <= k/2；

\* ==> k - (p+1) >= k - k/2。

显然，len1 >= k - (p+1) >= k/2 ，这与上面的假设，k/2 >= len1是矛盾的。

\*/

return findKth(nums1,start1,end1,nums2,start2+j,end2,k-j); //此时就是求第(k-j)小元素

\}else if(nums1\[start1+i-1\] < nums2\[start2+j-1\])\{ //此时 nums1\[start1,end1\]中就要舍弃前面i个元素

return findKth(nums1,start1+i,end1,nums2,start2,end2,k-i);

\}else\{

return nums1\[start1+i-1\];

三、对撞指针

\*1、两数之和-输出有序数组(167)

问题描述：给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值(index1 和 index2)不是从零开始的。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = \[2, 7, 11, 15\], target = 9

输出: \[1,2\]

解释:

2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

//几个问题

//1、\*\*如果没有解如何处理\*\*？ 题目保证有解

//2、\*\*如果有多个个如何处理\*\*？ 返回任意一组即可

//3、\*\*索引是从0开始还是从1开始\*\*？ 索引从1开始

//思路一：

// 数组有序，首先想到二分查找，对于nums\[i\]，如果数组中存在两个元素和为target，

// 则必然在nums\[i+1...n-1\]中存在元素target-nums\[i\]。

public int\[\] twoSum(int\[\] numbers, int target) \{

for(int i=0;i

int index=binarySearch(numbers,target-numbers\[i\],i+1,numbers.length-1);

if(index!=-1)\{

//说明\[i+1...n-1\]存在元素target-numbers\[i\]

return new int\[\]\{i+1,index+1\};

return null;

public int binarySearch(int\[\] numbers,int target,int l,int r)\{

while(l<=r)\{

int mid=(r-l)/2+l;

if(numbers\[mid\]==target)\{

return mid;

\}else if(numbers\[mid\]

l=mid+1;

\}else\{

r=mid-1;

return -1;

//时间复杂度 O(nlogn)

//空间复杂度 O(1)

//思路二：

//引入两个指针 i,j，分别指向该有序数组的头部和尾部：

//当numbers\[i\]+numbers\[j\]==target时, i、j就是所求的解

//当numbers\[i\]+numbers\[j\]

//当numbers\[i\]+numbers\[j\]==target时,说明值过大，要减小值，j减1

public int\[\] twoSum(int\[\] numbers, int target) \{

int i=0;

int j=numbers.length-1;

while(i

//i和j是不能相等的，因为反返回两个不同下标

int sum=numbers\[i\]+numbers\[j\];

if(sum==target)\{

return new int\[\]\{i+1,j+1\};

\}else if(sum

i++;

\}else\{

j--;

return null;

//时间复杂度：O(n)

//空间复杂度：O(1)

2、合并两个有序数组(88)

问题描述：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中\*，\*使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。

你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

输入:

nums1 = \[1,2,3,0,0,0\], m = 3

nums2 = \[2,5,6\], n = 3

输出: \[1,2,2,3,5,6\]

public void merge(int\[\] nums1, int m, int\[\] nums2, int n) \{

//新数组的下标

int index = m+n-1;

int i = m-1;

int j = n-1;

while(i>=0 && j>=0)\{

if(nums1\[i\] > nums2\[j\])\{

nums1\[index\] = nums1\[i--\];

\}else\{

nums1\[index\] = nums2\[j--\];

index--;

// nums1任然有未合并的元素，此时该操作可以省略，因为我们是使用num1存储结果的

//while(i>=0)\{

// nums1\[index--\] = nums1\[i--\];

//\}

// nums2任然有未合并的元素

while(j>=0)\{

nums1\[index--\] = nums2\[j--\];

3、平方数之和(633)

问题描述：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c。

示例1：

输入: 5

输出: True

解释: 1 \* 1 + 2 \* 2 = 5

示例2：

输入: 3

输出: False

public boolean judgeSquareSum(int c) \{

if(c==0)\{

return true;

int a = 0;

int b = (int)Math.sqrt(1.0\*c);

while(a<=b)\{

int C = a\*a + b\*b;

if(c == C)\{

return true;

\}else if(c >C)\{

a++;

\}else\{

assert c

b--;

return false;

4、验证回文串(125)

问题描述：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：

本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"

输出: true

示例 2:

输入: "race a car"

输出: false

//算法思路：对撞指针。只不过要注意遇到不是字母或者数字的字符要跳过，字符之间的比较是忽略大小写的

class Solution \{

public boolean isPalindrome(String s) \{

if(s.length()<=0)\{

return true;

char\[\] arr = s.toCharArray();

int i = 0;

int j = arr.length-1;

while(i<=j)\{

// 注意遇到不是字母或者数字的字符要跳过

if(!(Character.isDigit(arr\[i\]) || Character.isLetter(arr\[i\])))\{

i++;

continue;

if(!(Character.isDigit(arr\[j\]) || Character.isLetter(arr\[j\])))\{

j--;

continue;

//判断

if(isEqualChar(arr\[i\],arr\[j\]))\{

i++;

j--;

\}else\{

return false;

return true;

//判断这两个字符是否相等(忽略大小写)

private boolean isEqualChar(char c1,char c2)\{

if(c1!=c2)\{

if(Character.isLetter(c1) && Character.isLetter(c2) && Math.abs(c1-c2)!=32)\{

return false;

\}else if(Character.isLetter(c1) && Character.isDigit(c2))\{

return false;

\}else if(Character.isDigit(c1) && Character.isLetter(c2))\{

return false;

\}else if(Character.isDigit(c1) && Character.isDigit(c2))\{

return false;

return true;

//时间复杂度：O(n)

//空间复杂度：O(1)

5、验证回文字符串 Ⅱ(680)

问题描述：给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"

输出: True

示例 2:

输入: "abca"

输出: True

解释: 你可以删除c字符。

注意:字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

public boolean validPalindrome(String s) \{

int l = 0;

int r = s.length()-1;

while(l

if(s.charAt(l) != s.charAt(r))\{

return isPalindrome(s,l,r-1) || isPalindrome(s,l+1,r);

l++;

r--;

return true;

//判断字符串 s\[i,j\] 是否是回文串

private boolean isPalindrome(String s, int i, int j) \{

while (i < j) \{

if (s.charAt(i++) != s.charAt(j--)) \{

return false;

return true;

\*6、通过删除字母匹配到字典里最长单词(524)

问题描述：给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。

示例 1:

输入:

s = "abpcplea", d = \["ale","apple","monkey","plea"\]

输出:

"apple"

示例 2：

输入:

s = "abpcplea", d = \["a","b","c"\]

输出:

"a"

说明:

所有输入的字符串只包含小写字母。

字典的大小不会超过 1000。

所有输入的字符串长度不会超过 1000。

public String findLongestWord(String s, List d) \{

String longestWord = ""; //当前在字典中最长的单词

for(String word : d)\{

int l1 = longestWord.length();

int l2 = word.length();

if((l1>l2) ||

(l1==l2 && longestWord.compareTo(word)<0))\{

//longWord 单词已经比 word 单词长了，不考虑该 word

//longWord 和 word 一样长，但是 longWord 字典顺序更小，也不考虑该 word

continue;

if(isValid(s,word))\{

longestWord = word;

return longestWord;

//TODO：判断 word 是否通过删除 s 的某些字符来得到。

private boolean isValid(String s,String word)\{

int i=0,j=0;

while(i

if(s.charAt(i) == word.charAt(j))\{

j++;

i++;

return j == word.length();

7、反转字符串(344)

问题描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char\[\] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：

输入：\["h","e","l","l","o"\]

输出：\["o","l","l","e","h"\]

示例 2：

输入：\["H","a","n","n","a","h"\]

输出：\["h","a","n","n","a","H"\]

//时间复杂度：O(n)

class Solution \{

public void reverseString(char\[\] s) \{

if(s.length<=1)\{

return;

int i = 0;

int j = s.length-1;

while(i

char tmp = s\[i\];

s\[i\] = s\[j\];

s\[j\] = tmp;

i++;

j--;

8、反转字符串中元音字母(345)

问题描述：编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1:

输入: "hello"

输出: "holle"

示例 2:

输入: "leetcode"

输出: "leotcede"

class Solution \{

public String reverseVowels(String s) \{

if(s.length()<=1)\{

return s;

char\[\] chs = s.toCharArray();

int i =0;

int j =chs.length-1;

while(i

if(isVowels(chs\[i\]) && isVowels(chs\[j\]))\{

char tmp = chs\[i\];

chs\[i\] = chs\[j\];

chs\[j\] = tmp;

i++;

j--;

\}else if(isVowels(chs\[i\]) && !isVowels(chs\[j\]))\{

j--;

\}else if(!isVowels(chs\[i\]) && isVowels(chs\[j\]))\{

i++;

\}else\{

i++;

j--;

return new String(chs,0,chs.length);

//判断该字符是否是元音字母

private boolean isVowels(char c)\{

if((c=='a'|| c=='e'|| c=='i'||c=='o'||c=='u' ) ||

(c=='A'||c=='E'||c=='I'||c=='O'||c=='U'))\{

return true;

return false;

\*9、盛水最多的容器(11)

问题描述：给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

![da2352af257ea16b8ef14c31f8db899d.png][]

示例:

输入: \[1,8,6,2,5,4,8,3,7\]

输出: 49

//思路：对撞指针

//假设有左指针和右指针，且左指针指向的值小于右指针的值。

//假如我们将右指针左移，则右指针左移后的值和左指针指向的值相比有三种情况：

//(1)右指针指向的值大于左指针：这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小

//(2)右指针指向的值等于左指针：这种情况下，容器的高取决于左指针，但是底变短了，所以容器盛水量一定变小

//(3)右指针指向的值小于左指针：这种情况下，容器的高取决于右指针，但是右指针小于左指针，且底也变短了，所以容量盛水量一定变小了

// 反之，情况类似。

// 综上所述，容器高度较大的一侧的移动只会造成容器盛水量减小。

// 所以应当移动高度较小一侧的指针，并继续遍历，直至两指针相遇。

class Solution \{

public int maxArea(int\[\] height) \{

if(height.length<=1)\{

return 0;

int l = 0;

int r = height.length-1;

int max = 0;

while(l

//如何判断判断时想左以，还是向右移

int tmp = (r-l)\*Math.min(height\[l\],height\[r\]);

if(tmp > max)\{

max = tmp;

if(height\[l\]

l++;

\}else\{

r--;

return max;

四、滑动窗口

\*1、长度最小的子数组(209)

问题描述：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例:

输入: s = 7, nums = \[2,3,1,2,4,3\]

输出: 2

解释: 子数组 \[4,3\] 是该条件下的长度最小的连续子数组。

进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

//思路：

//l=0,r=-1(一开始不包含任何元素，所以取l=0,r=-1),

//滑动窗口\[l,r\] ,sum是\[l...r\]的和：

//当sum

class Solution \{

public int minSubArrayLen(int s, int\[\] nums) \{

int n=nums.length;

int l=0,r=-1;

//\[l,r\]为滑动窗口，开始时不包含任何元素

int sum=0;

//记录滑动窗口中元素和

int ret=n+1;

//ret记录求解的长度

while(l

if(r+1

r++;

sum+=nums\[r\];

\}else\{

sum-=nums\[l\];

l++;

if(sum>=s)\{

ret=Math.min(ret,(r-l+1));

//TODO:不能忽视无解的情况

if(ret==n+1)\{

//表示没有找到结果，使得 sum>=s

ret=0;

return ret;

\*2、无重复字符的最长子串(3)

问题描述：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

//思路一：暴力解法，但是超过时间限制

public int lengthOfLongestSubstring(String s) \{

int res = 0;

for(int i=0;i

for(int j=i+1;j<= s.length();j++)\{

String tmp = s.substring(i,j);

if(contains(tmp))\{

res = Math.max(res,tmp.length());

return res;

//判断字符串s是否包含重复元素

//返回true,说明包含重复元素

private boolean contains(String s)\{

char\[\] buf = s.toCharArray();

Set set = new HashSet<>();

for(char c : buf)\{

if(set.contains(c))\{

return false;

set.add(c);

return true;

//思路二：滑动窗口解法

//1、l=0,r=-1,\[l,r\]是滑动窗口，freq\[256\]数组用于判断该滑动窗口是否存在重复元素：

//2、当加入的元素不是重复元素时,r+1，扩展该窗口

//3、其他情况，缩小该窗口，l+1

public int lengthOfLongestSubstring(String s) \{

int l = 0, r = -1;

int\[\] freq = new int\[256\];

int n =s.length();

//记录最长长度

int res = 0;

while(l

if(r+1 < n && freq\[s.charAt(r+1)\]==0)\{ //扩展窗口

r++;

freq\[s.charAt(r)\]++;

\}else\{ //缩小窗口

freq\[s.charAt(l)\]--;

l++;

res = Math.max(res,r-l+1);

return res;

3、找到字符串中所有字母异位词(438)

问题描述：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：字母异位词指字母相同，但排列不同的字符串。不考虑答案输出的顺序。

示例 1:

输入:

s: "cbaebabacd" p: "abc"

输出:

\[0, 6\]

解释:

起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。

起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

示例 2:

输入:

s: "abab" p: "ab"

输出:

\[0, 1, 2\]

解释:

起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。

起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。

起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

//思路一：固定该滑动窗口大小，逐步平移该窗口

class Solution \{

public List findAnagrams(String s, String p) \{

List res = new ArrayList<>();

int l = 0;

int r = p.length();

//\[l,r) 范围内字符,组成字符串

while (r<=s.length())\{

String newP = s.substring(l,r);

if(isAnagram(newP,p))\{

res.add(l);

l++;

r++;

return res;

//判断两个字符串是否是Anagram

//先判断长度是否相同，不相同，直接返回false

//统计 s1字符串中每个小写字母出现的频率，根据s2是否出现相同的字母以及出现的字母的频率是否相同

private boolean isAnagram(String word1,String word2)\{

if(word1.length() != word2.length())\{

return false;

int\[\] freq = new int\[26\];

for(int i=0;i

freq\[word1.charAt(i)-'a'\]++;

for(int i=0;i

char c = word2.charAt(i);

if(freq\[c-'a'\]==0)\{

// word1 不包括字符 c，但是 word2 包括，则 word1 和 word2 必然不是字母异位词

return false;

freq\[c-'a'\]--;

return true;

class Solution \{

public List findAnagrams(String s, String p) \{

List ret = new ArrayList<>();

if (s == null || s == "") \{

return ret;

//统计字符串p中出现的小写字符的频率

int\[\] pFreq=new int\[256\];

//count是p中的字符数

int count=p.length();

for(int i=0;i

pFreq\[p.charAt(i)\]++;

int l=0,r=0;

//\[l,r)表示滑动窗口

while(r

if(pFreq\[s.charAt(r++)\]-->=1)\{

//每次有一个p中字符进入窗口，扩展窗口，并且count–1

count--;

if(count==0)\{

//当count == 0的时候，表明我们的窗口中包含了p中的全部字符，得到一个结果。

ret.add(l);

if (r-l == p.length()) \{

//当窗口包含一个结果以后，为了进一步遍历，我们需要缩小窗口使窗口不再包含全部的p，

//同样，如果pFreq\[char\]>=0，表明一个在p中的字符就要从窗口移动到p字符串中，那么count ++

if (pFreq\[s.charAt(l++)\]++ >= 0) \{

count++; // one more needed to match

return ret;

4、最小覆盖子串(76)

问题描述：给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"

输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。

如果 S 中存在这样的子串，我们保证它是唯一的答案。

/\*\*

\* 思路：

\* 我们可以考虑哈希表，其中key是T中的字符，value是该字符出现的次数。

\- 我们最开始先扫描一遍T，把对应的字符及其出现的次数存到哈希表中。

\- 然后开始遍历S，遇到T中的字符，就把对应的哈希表中的value减一，

直到包含了T中的所有的字符，纪录一个字串并更新最小字串值。

\- 将子窗口的左边界向右移，略掉不在T中的字符，

如果某个在T中的字符出现的次数大于哈希表中的value，则也可以跳过该字符。

\*/

public String minWindow(String s, String t) \{

if(s.length()

return "";

//统计t中字符的出现次数

Map map=new HashMap<>();

for(int i=0;i

int freq=map.getOrDefault(t.charAt(i),0);

map.put(t.charAt(i),++freq);

int l=0,r=0;

//\[l,r\]为滑动窗口，开始时，没有元素

int count=0;

//在窗口中出现的字符串T中的元素个数

String ret="";

int minLen=s.length()+1;

//记录最长子段的长度

while(r

//s.charAt(r)表示s中字符

if(map.containsKey(s.charAt(r)))\{

int freq=map.get(s.charAt(r));

map.put(s.charAt(r),--freq);

//count统计字符串s中t中字符出现的次数

if(freq>=0)\{

count++;

//s中出现的字符数刚好包含了t中所有的字符

while (count == t.length()) \{

//\[l...r\]窗口就是最字符串短

if (r - l + 1 < minLen) \{

minLen = r - l + 1;

ret = s.substring(l, r + 1);

//缩小窗口

if (map.containsKey(s.charAt(l))) \{

int sfreq = map.get(s.charAt(l));

map.put(s.charAt(l), ++sfreq);

if (sfreq > 0) \{

\--count;

\++l;

r++;

return ret;

5、乘积小于k的子数组(713)

问题描述：给定一个正整数数组 nums。找出该数组内乘积小于 k 的连续的子数组的个数。

示例 1:

输入: nums = \[10,5,2,6\], k = 100

输出: 8

解释: 8个乘积小于100的子数组分别为: \[10\], \[5\], \[2\], \[6\], \[10,5\], \[5,2\], \[2,6\], \[5,2,6\]。

需要注意的是 \[10,5,2\] 并不是乘积小于100的子数组。

说明:

0 < nums.length <= 50000

0 < nums\[i\] < 1000

0 <= k < 10^6

/\*\*

\* 思路：

\* 采用滑动窗口的解法：维护一个数字乘积刚好小于k的滑动窗口窗口，

\* 用变量l来记录其左边界的位置，右边界r就是当前遍历到的位置。

\* 遍历原数组，用product乘上当前遍历到的数字，

\* 然后进行while循环，如果product大于等于k，

\* 则滑动窗口的左边界需要向右移动一位，删除最左边的数字，那么少了一个数字，乘积就会改变，

\* 所以用product除以最左边的数字，然后左边右移一位，即l自增1。

\* 当我们确定了窗口的大小后，就可以统计子数组的个数了，就是窗口的大小。

\* 为什么子数组的个数就是窗口的大小？

\* 比如\[5 2 6\]这个窗口，k还是100，右边界刚滑到6这个位置，

\* 这个窗口的大小就是包含6的子数组乘积小于k的个数，即\[6\], \[2 6\], \[5 2 6\]，正好是3个。

\* 所以窗口每次向右增加一个数字，然后左边去掉需要去掉的数字后，

\* 窗口的大小就是新的子数组的个数，每次加到结果res中即可。

\* 注意：

\* 这里要求子集的乘积值必须小于k

\*/

class Solution \{

public int numSubarrayProductLessThanK(int\[\] nums, int k) \{

if(k<=1)\{

return 0;

int l=0;

int r=0;

int res=0;

//\[l..r\]表示的是乘积和

int product=1;

while(r

product\*=nums\[r\];

while(product>=k)\{

product/=nums\[l\];

l++;

//r-l+1表示的就是\[l...r\]窗口的长度

res+=(r-l+1);

r++;

return res;

五、矩阵

1、重塑矩阵(566)

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

示例 1:

输入:

nums =

\[\[1,2\],

\[3,4\]\]

r = 1, c = 4

输出:

\[\[1,2,3,4\]\]

解释:

行遍历nums的结果是 \[1,2,3,4\]。新的矩阵是 1 \* 4 矩阵, 用之前的元素值一行一行填充新矩阵。

示例 2:

输入:

nums =

\[\[1,2\],

\[3,4\]\]

r = 2, c = 4

输出:

\[\[1,2\],

\[3,4\]\]

解释:

没有办法将 2 \* 2 矩阵转化为 2 \* 4 矩阵。 所以输出原矩阵。

注意：

给定矩阵的宽和高范围在 \[1, 100\]。

给定的 r 和 c 都是正数。

public int\[\]\[\] matrixReshape(int\[\]\[\] nums, int r, int c) \{

int m = nums.length;

if(m == 0)\{

return null;

int n = nums\[0\].length;

if(m \* n != r \* c)\{ //不符合条件，就输出原矩阵

return nums;

int\[\]\[\] res = new int\[r\]\[c\];

int index = 0; // index 在\[0,m\*n-1\] 范围内

for(int i=0;i

for(int j=0;j

res\[i\]\[j\] = nums\[index/n\]\[index%n\];

index++;

return res;

2、搜索二维矩阵II(240)

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。

每列的元素从上到下升序排列。

示例:

现有矩阵 matrix 如下：

\[1, 4, 7, 11, 15\],

\[2, 5, 8, 12, 19\],

\[3, 6, 9, 16, 22\],

\[10, 13, 14, 17, 24\],

\[18, 21, 23, 26, 30\]

给定 target = 5，返回 true。

给定 target = 20，返回 false。

public boolean searchMatrix(int\[\]\[\] matrix, int target) \{

int row = matrix.length;

if(row == 0)\{

return false;

int col = matrix\[0\].length;

for(int i=row-1,j=0;i>= 0 && j

if(matrix\[i\]\[j\] == target)\{

return true;

\}else if(matrix\[i\]\[j\] < target)\{

j++;

\}else\{

assert matrix\[i\]\[j\] > target;

i--;

return false;

3、有序矩阵的第 K 小元素 (378)

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。

请注意，它是排序后的第k小元素，而不是第k个元素。

示例:

matrix = \[

\[ 1, 5, 9\],

\[10, 11, 13\],

\[12, 13, 15\]

\],

k = 8,

返回 13。

说明:

你可以假设 k 的值永远是有效的, 1 ≤ k ≤ n2 。

二分查找解法：

// 参考 287 题

public int kthSmallest(int\[\]\[\] matrix, int k) \{

int n = matrix.length;

int lo = matrix\[0\]\[0\];

int hi = matrix\[n-1\]\[n-1\];

while (lo <= hi)\{

int mid = lo + (hi-lo)/2;

int cnt = 0;

//TODO：统计矩阵中 <= mid 的元素个数

//(实际上是用来进行切分的)

for(int i=0;i

for(int j=0;j

cnt++;

if(cnt < k)\{ // 说明 mid 左边 不够 k 小个元素

lo = mid+1;

\}else\{

hi = mid-1;

return lo;

堆解法：

public int kthSmallest(int\[\]\[\] matrix, int k) \{

int n = matrix.length;

// Java 默认是小根堆

PriorityQueue pq = new PriorityQueue<>(new Comparator() \{

@Override

public int compare(Integer o1, Integer o2) \{

return o2-o1;

\});

for(int i=0;i

for(int j=0;j

pq.add(matrix\[i\]\[j\]);

if(pq.size() > k)\{

pq.poll();

return pq.peek();

\*4、螺旋矩阵(54)

给定一个包含 m x n 个元素的矩阵(m 行, n 列)，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:

\[ 1, 2, 3 \],

\[ 4, 5, 6 \],

\[ 7, 8, 9 \]

输出: \[1,2,3,6,9,8,7,4,5\]

示例 2:

输入:

\[1, 2, 3, 4\],

\[5, 6, 7, 8\],

\[9,10,11,12\]

输出: \[1,2,3,4,8,12,11,10,9,5,6,7\]

public List spiralOrder(int\[\]\[\] matrix) \{

List res = new ArrayList<>();

if(matrix == null)\{

return res;

int m = matrix.length;

if(m == 0)\{

return res;

int n = matrix\[0\].length;

int top = 0 , down = m-1;

int left = 0, right = n-1;

while(top<=down && left<=right)\{

// top == down 针对奇数行的情况；left == right 针对奇数列的情况。

//从左向右遍历

for(int j = left; j <= right ; j++)\{

res.add(matrix\[top\]\[j\]);

top++;

//从上向下遍历

for(int i = top; i<= down; i++)\{

res.add(matrix\[i\]\[right\]);

right--;

//从右向左遍历

if(top <= down)\{

//因为之前 top++，top 值发生了变化，如果 top > down，就不需要遍历了

for(int j = right;j>=left;j--)\{

res.add(matrix\[down\]\[j\]);

down--;

//从下往上遍历

if(left <= right)\{

//因为之前 right--，right 值发生了变化，如果 left > right，就不需要遍历了

for(int i=down;i>=top;i--)\{

res.add(matrix\[i\]\[left\]);

left++;

return res;

5、螺旋矩阵II(59)

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

示例:

输入: 3

输出:

\[ 1, 2, 3 \],

\[ 8, 9, 4 \],

\[ 7, 6, 5 \]

public int\[\]\[\] generateMatrix(int n) \{

int\[\]\[\] res = new int\[n\]\[n\];

int k = 1;

int top = 0 , down = n-1;

int left = 0, right = n-1;

while(top<=down && left<=right)\{

// top == down 针对奇数行的情况；left == right 针对奇数列的情况。

//从左向右遍历

for(int j = left; j <= right ; j++)\{

res\[top\]\[j\] = k++;

top++;

//从上向下遍历

for(int i = top; i<= down; i++)\{

res\[i\]\[right\] = k++;

right--;

//从右向左遍历

if(top <= down)\{

//因为之前 top++，top 值发生了变化，如果 top > down，就不需要遍历了

for(int j = right;j>=left;j--)\{

res\[down\]\[j\] = k++;

down--;

//从下往上遍历

if(left <= right)\{

//因为之前 right--，right 值发生了变化，如果 left > right，就不需要遍历了

for(int i=down;i>=top;i--)\{

res\[i\]\[left\] = k++;

left++;

return res;

6、螺旋矩阵III(885)

在 R 行 C 列的矩阵上，我们从 (r0, c0) 面朝东面开始

这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。

现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。

每当我们移动到网格的边界之外时，我们会继续在网格之外行走(但稍后可能会返回到网格边界)。

最终，我们到过网格的所有 R \* C 个空间。

按照访问顺序返回表示网格位置的坐标列表。

示例 1：

输入：R = 1, C = 4, r0 = 0, c0 = 0

输出：\[\[0,0\],\[0,1\],\[0,2\],\[0,3\]\]

![87244b745107467605061c7614c09f0c.png][]

示例 2：

输入：R = 5, C = 6, r0 = 1, c0 = 4

输出：\[\[1,4\],\[1,5\],\[2,5\],\[2,4\],\[2,3\],\[1,3\],\[0,3\],\[0,4\],\[0,5\],\[3,5\],\[3,4\],\[3,3\],\[3,2\],\[2,2\],\[1,2\],\[0,2\],\[4,5\],\[4,4\],\[4,3\],\[4,2\],\[4,1\],\[3,1\],\[2,1\],\[1,1\],\[0,1\],\[4,0\],\[3,0\],\[2,0\],\[1,0\],\[0,0\]\]

![cf63717c65f2be4510669e06493cd089.png][]

提示：

1 <= R <= 100

1 <= C <= 100

0 <= r0 < R

0 <= c0 < C

public int\[\]\[\] spiralMatrixIII(int R, int C, int r0, int c0) \{

int\[\]\[\] res = new int\[R\*C\]\[2\];

int k = 1;

int step=1; //每次螺旋的步长，第一次是1，第二次就是2

int posx=r0,posy=c0; //(posx,posy)是每次螺旋的起始位置

//(posx,posy) 就是第一个元素的位置

res\[0\]\[0\] = posx;

res\[0\]\[1\] = posy;

int curD=0; //curD是螺旋的方向，curD初始值为0，表示是从右开始的

while(k

for(int i=0;i<2;i++)\{ //四次螺旋，分别有两次的步数是一样的

for(int j=0;j

posx+=d\[curD\]\[0\];

posy+=d\[curD\]\[1\];

if(inArea(R,C,posx,posy))\{

res\[k\]\[0\] = posx;

res\[k\]\[1\] = posy;

k++;

//每次螺旋，都要换方向。螺旋四次后，又是从右边开始

//右 -> 下 -> 左 -> 上

curD=(curD+1)%4;

step++;

return res;

//注意：这里不是坐标，是该二维数组下标。

private int\[\]\[\] d=\{

\{0,1\}, //向右

\{1,0\}, //向下

\{0,-1\}, //向左

\{-1,0\}, //向上

\};

//判断下标是否在该矩阵内

private boolean inArea(int R,int C,int x,int y)\{

return (x>=0 && x=0 && y

7、范围求和III(598)

给定一个初始元素全部为 0，大小为 m\*n 的矩阵 M 以及在 M 上的一系列更新操作。

操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M\[i\]\[j\] 的值都增加 1。

在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

示例 1:

输入:

m = 3, n = 3

operations = \[\[2,2\],\[3,3\]\]

输出: 4

解释:

初始状态, M =

\[\[0, 0, 0\],

\[0, 0, 0\],

\[0, 0, 0\]\]

执行完操作 \[2,2\] 后, M =

\[\[1, 1, 0\],

\[1, 1, 0\],

\[0, 0, 0\]\]

执行完操作 \[3,3\] 后, M =

\[\[2, 2, 1\],

\[2, 2, 1\],

\[1, 1, 1\]\]

M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。

注意:

m 和 n 的范围是 \[1,40000\]。

a 的范围是 \[1,m\]，b 的范围是 \[1,n\]。

操作数目不超过 10000。

//思路：

//只需要找出两个操作的重叠区域，由于每次操作都是+1

//所有最大值就是： 重叠区域长\*重叠区域宽

public int maxCount(int m, int n, int\[\]\[\] ops) \{

if( m ==0 || n==0)\{

return 0;

int row = m; // row 表示重叠区域长

int col = n; // col 表示重叠区域宽

for(int i=0;i

row = Math.min(row,ops\[i\]\[0\]);

col = Math.min(col,ops\[i\]\[1\]);

return row\*col;

8、托普利茨矩阵(766)

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素，那么这个矩阵是托普利茨矩阵。

给定一个 M x N 的矩阵，当且仅当它是托普利茨矩阵时返回 True。

示例 1:

输入:

matrix = \[

\[1,2,3,4\],

\[5,1,2,3\],

\[9,5,1,2\]

输出: True

解释:

在上述矩阵中, 其对角线为:

"\[9\]", "\[5, 5\]", "\[1, 1, 1\]", "\[2, 2, 2\]", "\[3, 3\]", "\[4\]"。

各条对角线上的所有元素均相同, 因此答案是True。

示例 2:

输入:

matrix = \[

\[1,2\],

\[2,2\]

输出: False

解释:

对角线"\[1, 2\]"上的元素不同。

说明:

matrix 是一个包含整数的二维数组。

matrix 的行数和列数均在 \[1, 20\]范围内。

matrix\[i\]\[j\] 包含的整数在 \[0, 99\]范围内。

进阶:

如果矩阵存储在磁盘上，并且磁盘内存是有限的，因此一次最多只能将一行矩阵加载到内存中，该怎么办？

如果矩阵太大以至于只能一次将部分行加载到内存中，该怎么办？

//思路一

public boolean isToeplitzMatrix(int\[\]\[\] matrix) \{

int m=matrix.length;

int n=matrix\[0\].length;

for(int i=1;i

for(int j=1;j

if(matrix\[i-1\]\[j-1\]!=matrix\[i\]\[j\])\{

return false;

return true;

//思路二

public boolean isToeplitzMatrix(int\[\]\[\] matrix) \{

for (int i = 0; i < matrix\[0\].length; i++) \{

if (!check(matrix, matrix\[0\]\[i\], 0, i)) \{

return false;

for (int i = 0; i < matrix.length; i++) \{

if (!check(matrix, matrix\[i\]\[0\], i, 0)) \{

return false;

return true;

private boolean check(int\[\]\[\] matrix, int expectValue, int row, int col) \{

if (row >= matrix.length || col >= matrix\[0\].length) \{

return true;

if (matrix\[row\]\[col\] != expectValue) \{

return false;

return check(matrix, expectValue, row + 1, col + 1);

[da2352af257ea16b8ef14c31f8db899d.png]: /images/20221023/21aaf2912d994922babf2806066f734a.png
[87244b745107467605061c7614c09f0c.png]: /images/20221023/9009c669ac4f41fbb1f3eff469a78917.png
[cf63717c65f2be4510669e06493cd089.png]: /images/20221023/0358c38b01144ea69a53e0103c6b23e6.png