1.数组

（1）找到所有数组中消失的数字(448)

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]输入：nums = [1,1]
输出：[2]

//时间空间复杂度都为O(n)
public class Solution {public static void main(String[] args) {int[] arr={4,3,2,7,8,2,3,1};Solution solution=new Solution();System.out.println(solution.findDisappearedNumbers(arr));}public List<Integer> findDisappearedNumbers(int[] nums) {int n= nums.length;boolean[] find=new boolean[n+1];//数组中出现的数将该数对应的数组位置置为trueList<Integer> list=new ArrayList<>();for (int i=0;i<n;i++){find[nums[i]]=true;}for (int i=1;i<=n;i++){if (!find[i]){list.add(i);}}return list;}
}//空间复杂度为O(1)
public class Solution {public static void main(String[] args) {int[] arr={4,3,2,7,8,2,3,1};Solution solution=new Solution();System.out.println(solution.findDisappearedNumbers(arr));}public List<Integer> findDisappearedNumbers(int[] nums) {int n= nums.length;List<Integer> list=new ArrayList<>();//遍历数组 每遇到一个数x 就让nums[x-1]增加n//当我们遍历到某个位置时 其中的数可能已经被增加过了 因此需要对n取模for (int i=0;i<n;i++){int x=(nums[i]-1)%n;nums[x]+=n;}//遍历nums 若nums[i]未大于n 就说明没有遇到过数i+1for (int i=0;i<n;i++){if (nums[i]<=n){list.add(i+1);}}return list;}
}

（2）旋转图像(48)

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

对应位置交换位置，结束条件可以考虑i和j同时向内缩进，也就是一圈一圈考虑

public class Solution {public static void main(String[] args) {int[][] arr={{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};Solution solution=new Solution();solution.rotate(arr);for (int i=0;i<arr.length;i++){for (int j=0;j< arr[0].length;j++){System.out.print(arr[i][j]+" ");}System.out.println();}}public void rotate(int[][] matrix) {int rowMin=0;//从第0行开始 起始行int colMin=0;//从第0列开始 起始列int rowMax= matrix.length-1;//第一圈可以用到的的最大行数是总行数-1int colMax=matrix[0].length-1;//第一圈可以用到的的最大列数是总列数-1//旋转完一圈开始下一圈 循环退出条件是 起始行>最大行 起始列>最大列while (rowMin<=rowMax&&colMin<=colMax){RotateOneCircle(matrix,rowMin,colMin,rowMax,colMax);//缩进rowMin++;colMin++;rowMax--;colMax--;}}//旋转一圈的方法private void RotateOneCircle(int[][] arr, int rowMin, int colMin, int rowMax, int colMax) {int temp=0;//辅助数//遍历旋转这一圈for (int j=0;j<colMax-colMin;j++){temp=arr[rowMin][colMin+j];arr[rowMin][colMin+j]=arr[rowMax-j][colMin];arr[rowMax-j][colMin]=arr[rowMax][colMax-j];arr[rowMax][colMax-j]=arr[rowMin+j][colMax];arr[rowMin+j][colMax]=temp;}}
}

（3）搜索二维矩阵 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大于当前元素，则用当前元素下方的元素再次比较；如果target小于当前元素，
则用当前元素左边的元素再次比较；以此类推，知道找到target或者到达边界

public class Solution {public static void main(String[] args) {int[][] arr={{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}};int target=5;Solution solution=new Solution();System.out.println(solution.searchMatrix(arr,5));}public boolean searchMatrix(int[][] matrix, int target) {int m= matrix.length;int n=matrix[0].length-1;//表示列int i=0;//表示行while (i<m&&n>=0){if (target>matrix[i][n]){//target大于当前元素 比较下方元素i++;} else if (target<matrix[i][n]) {//target小于当前元素 比较左方元素n--;}else {//找到targetreturn true;}}return false;}
}

（4）最多能完成排序的块(769)

给定一个长度为 n 的整数数组 arr ，它表示在 [0, n - 1] 范围内的整数的排列。
我们将 arr 分割成若干 块 (即分区)，并对每个块单独排序。将它们连接起来后，使得连接的结果和按升序排序后的原数组相同。
返回数组能分成的最多块数量。

输入: arr = [4,3,2,1,0]
输出: 1
解释:
将数组分成2块或者更多块，都无法得到所需的结果。
例如，分成 [4, 3], [2, 1, 0] 的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。输入: arr = [1,0,2,3,4]
输出: 4
解释:
我们可以把它分成两块，例如 [1, 0], [2, 3, 4]。
然而，分成 [1, 0], [2], [3], [4] 可以得到最多的块数。
对每个块单独排序后，结果为 [0, 1], [2], [3], [4]

public class Solution {public static void main(String[] args) {int[] arr={1,0,2,3,4};Solution solution=new Solution();System.out.println(solution.maxChunksToSorted(arr));}public int maxChunksToSorted(int[] arr) {int n=arr.length;if (arr.length==1){return 1;}int maxCount=0;//可以分成的最大块数int preMax=0;//当前最大值for (int i=0;i<n;i++){preMax=Math.max(preMax,arr[i]);//如果当前最大值等于当前的i值if (preMax==i){maxCount++;//可以分块数+1}}return maxCount;}
}

2.栈和队列

（1）用栈实现队列(232)

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

public class MyQueue {Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue() {stack1=new Stack<>();stack2=new Stack<>();}public void push(int x) {while (!stack2.isEmpty()){stack1.push(stack2.pop());}stack1.push(x);}public int pop() {if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {if (stack1.empty()&& stack2.empty()){return true;}return false;}
}public class QueueTest {public static void main(String[] args) {MyQueue queue=new MyQueue();queue.push(1);queue.push(2);queue.push(3);//System.out.println("pop():"+queue.pop());System.out.println("peak():"+queue.peek());System.out.println("empty():"+queue.empty());queue.push(4);System.out.println("====================");System.out.println("pop():"+queue.pop());System.out.println("peak():"+queue.peek());System.out.println("empty():"+queue.empty());}}

（2）最小栈(155)

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

public class MinStack {Stack<Integer> stack;//普通栈Stack<Integer> minStack;//返回最小值的栈public MinStack() {stack=new Stack<>();minStack=new Stack<>();minStack.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);//最小值栈保存当前元素加进来后 栈中的最小值minStack.push(Math.min(minStack.peek(),val));}public void pop() {stack.pop();//当前元素出栈时 最小值栈对应的位置也要出栈minStack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}}public class MinStackTest {public static void main(String[] args) {MinStack stack=new MinStack();stack.push(-3);stack.push(1);stack.push(23);System.out.println(stack.getMin());}}

（3）有效的括号(20)

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

输入：s = "()"
输出：true输入：s = "()[]{}"
输出：true输入：s = "(]"
输出：false

public class Solution {public static void main(String[] args) {String s="()[]{}";Solution solution=new Solution();System.out.println(solution.isValid(s));}public boolean isValid(String s) {int n=s.length();//长度为奇数直接返回falseif (n%2!=0){return false;}Stack<Character> stack=new Stack<>();Map<Character,Character> map=new HashMap<>();//将右括号和左括号分别以 key 和 value 存储map.put(')','(');map.put('}','{');map.put(']','[');//遍历字符串匹配括号for (int i=0;i<n;i++){char ch=s.charAt(i);if (map.containsKey(ch)){//如果ch是map集合里的key 也就是右括号//先判断stack是否为空或者栈顶元素是否与ch匹配if (stack.isEmpty()||stack.peek()!=map.get(ch)){return false;}//如果匹配stack.pop();//弹出栈顶括号}else {//如果ch是左括号stack.push(ch);}}return stack.isEmpty();}
}

3.单调栈

（1）每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]输入: temperatures = [30,60,90]
输出: [1,1,0]

public class Solution {public static void main(String[] args) {int[] arr={73,74,75,71,69,72,76,73};Solution solution=new Solution();int[] tem = solution.dailyTemperatures(arr);for (int i=0;i< tem.length;i++){System.out.print(tem[i]+" ");}}public int[] dailyTemperatures(int[] temperatures) {int n = temperatures.length;if (n==1){return new int[1];}int[] arr=new int[n];Stack<Integer> stack=new Stack<>();for (int i=0;i<n;i++){//当栈不为空并且栈顶温度小于当前温度时while (!stack.isEmpty()&&temperatures[i]>temperatures[stack.peek()]){arr[stack.peek()]=i-stack.pop();}//当上边两个条件不全满足时 将当前元素的下标入栈stack.push(i);}return arr;}
}

4.优先队列

（1）合并K个升序链表(23)

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6输入：lists = []
输出：[]输入：lists = [[]]
输出：[]

//顺序遍历合并每一个链表
public class Solution {public ListNode mergeKLists(ListNode[] lists) {ListNode list=null;//需要返回的链表//遍历每一个链表 然后与list合并for (int i=0;i< lists.length;i++){list=mergeTwoLists(lists[i],list);}return list;}private ListNode mergeTwoLists(ListNode a,ListNode b){if (a==null||b==null){return a!=null?a:b;}ListNode head=new ListNode(0);//设置一个头节点 返回的时候返回他的next节点ListNode tail=head;//记录下一个插入位置的前一个位置ListNode preA=a;//a链表的当前节点ListNode preB=b;//b链表的当前节点while (preA!=null&&preB!=null){if (preA.val<preB.val){tail.next=preA;preA=preA.next;}else {tail.next=preB;preB=preB.next;}tail=tail.next;}tail.next=preA!=null?preA:preB;return head.next;}
}//采用分治合并
public class Solution {public ListNode mergeKLists(ListNode[] lists) {return merge(lists,0,lists.length-1);}private ListNode merge(ListNode[] lists,int left,int right){if (left==right){return lists[left];}if (left>right){return null;}int mid=(left+right)>>1;//因为lists.length<500 所以这里不用担心越界 可以使用left+rightreturn mergeTwoLists(merge(lists, left, mid),merge(lists, mid+1, right));}private ListNode mergeTwoLists(ListNode a,ListNode b){if (a==null||b==null){return a!=null?a:b;}ListNode head=new ListNode(0);//设置一个头节点 返回的时候返回他的next节点ListNode tail=head;//记录下一个插入位置的前一个位置ListNode preA=a;//a链表的当前节点ListNode preB=b;//b链表的当前节点while (preA!=null&&preB!=null){if (preA.val<preB.val){tail.next=preA;preA=preA.next;}else {tail.next=preB;preB=preB.next;}tail=tail.next;}tail.next=preA!=null?preA:preB;return head.next;}
} 

5.双端队列

（1）滑动窗口最大值(239)

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7输入：nums = [1], k = 1
输出：[1]

//优先队列
public class Solution {public static void main(String[] args) {int[] arr={1,3,-1,-3,5,3,6,7};int k=3;Solution solution=new Solution();int[] ints = solution.maxSlidingWindow(arr, k);for (int i:ints) {System.out.print(i+" ");}}public int[] maxSlidingWindow(int[] nums, int k) {int n= nums.length;int[] res=new int[n-k+1];//定义一个大根堆PriorityQueue<int[]> heap=new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if (o1[0]!=o2[0]){//如果元素值不相等 按照元素值降序排序return o2[0]-o1[0];}//如果元素值相等 按照索引值降序排序return o2[1]-o1[1];}});//将数组前k个元素加入大根堆for (int i=0;i<k;i++){heap.add(new int[]{nums[i],i});}res[0]=heap.peek()[0];//开始滑动窗口for (int i=k;i<n;i++){heap.add(new int[]{nums[i],i});//当前元素加入大根堆//如果此时最大值不在窗口内 就将堆顶元素移除 直到堆顶元素最大值在当前窗口内//此时堆顶元素就是当前窗口内的最大值while (heap.peek()[1]<=i-k){heap.poll();//弹出堆顶元素}res[i-k+1]=heap.peek()[0];}return res;}
}

6.哈希表

哈希表又称为散列表，使用O(n)的空间复杂度存储数据，通过hash函数映射位置，从而实现近似O(1)的时间
复杂度的插入、删除、查找等操作

（1）两数之和(1)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

//暴力遍历
class Solution {public static void main(String[] args) {int[] arr={2,7,11,15};int k=9;Solution solution=new Solution();int[] ints = solution.twoSum(arr, k);for (int i:ints) {System.out.print(i+" ");}}public int[] twoSum(int[] nums, int target) {int n= nums.length;for (int i=0;i<n-1;i++){for (int j=i+1;j<n;j++){if (nums[j]==target-nums[i]){return new int[]{i,j};}}}return new int[0];}
}//使用hash表
public class Solution {public static void main(String[] args) {int[] arr={2,7,11,15};int k=9;Solution solution=new Solution();int[] ints = solution.twoSum(arr, k);for (int i:ints) {System.out.print(i+" ");}}public int[] twoSum(int[] nums, int target) {int n= nums.length;Map<Integer,Integer> map=new HashMap<>();for (int i=0;i<n;i++){//如果map里存在一个key使它和当前值相加等于target 直接返回他们的下标if (map.containsKey(target-nums[i])){return new int[]{map.get(target-nums[i]),i};}map.put(nums[i],i);}return new int[0];}
}

（2）最长连续序列(128)

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

public class Solution {public static void main(String[] args) {int[] arr={100,4,200,1,3,2};Solution solution=new Solution();System.out.println(solution.longestConsecutive(arr));}public int longestConsecutive(int[] nums) {int n= nums.length;if (n==0){return 0;} else if (n==1) {return 1;}Set<Integer> set=new HashSet<>();int longestLen=0;//最长序列长度//将数组中元素加入set集合中 并去重for (int i=0;i<n;i++){set.add(nums[i]);}//遍历数组中每一个元素for (int i=0;i<n;i++){//当一个元素在数组中不存在前驱元素时 从这个元素出发才可以得到当前最长序列//如果存在前驱元素 那么从前驱元素开始 得到的序列长度一定大于从当前这个元素开始的序列长度if (!set.contains(nums[i]-1)){int curLen=1;//当前长度int curNum=nums[i];//当前元素//当当前元素存在后继元素时 当前长度+1while (set.contains(curNum+1)){curLen++;curNum++;}longestLen=Math.max(longestLen,curLen);}}return longestLen;}
}

（3）直线上最多的点数

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

输入：points = [[1,1],[2,2],[3,3]]
输出：3

public class Solution {public static void main(String[] args) {int[][] arr={{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};Solution solution=new Solution();System.out.println(solution.maxPoints(arr));}public int maxPoints(int[][] points) {int n=points.length;if (n<=2){return n;}int maxPoint=0;//最多有多少个点在同一条直线上for (int i=0;i<n;i++){//当共线点的数量 > n/2时 或者 共线点的数量 >= 当前点i之后所剩的点的数量时 就直接退出循环if (maxPoint>=n-i||maxPoint>n/2){break;}//用map集合来存储每个不同直线上共线点的个数Map<Integer,Integer> map=new HashMap<>();for (int j=i+1;j<n;j++){int x=points[j][0]-points[i][0];int y=points[j][1]-points[i][1];//当x=0或者y=0时 将不为0的一方设置为1if (x==0){y=1;} else if (y==0) {x=1;}else {//假设y始终为正数if (y<0){x=-x;y=-y;}//求x和y的最大公倍数int gcdXY=gcd(Math.abs(x),Math.abs(y));//化简x和yx/=gcdXY;y/=gcdXY;}//将x和y用一个正数表示 作为集合的keyint key=y+20001*x;if (map.containsKey(key)){//当集合中存在key时 点数+1map.put(key,map.get(key)+1);}else {//集合中不存在key时 将这个key加入集合map.put(key,1);}}int preMax=0;//当前i所在的最大点数//遍历当前的map集合 求出当前的最大值for (Map.Entry<Integer,Integer> entry: map.entrySet()){preMax=Math.max(preMax, entry.getValue()+1);}//将每一次的当前最大值与最大值做比较 求总的最大值maxPoint=Math.max(preMax,maxPoint);}return maxPoint;}private int gcd(int x,int y){return y!=0?gcd(y,x%y):x;}
}

7.前缀和与积分图

（1）区域和检索 - 数组不可变(303)

给定一个整数数组 nums，处理以下类型的多个查询:
计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )

//暴力
public class NumArray {int[] arr;public NumArray(int[] nums) {this.arr=nums;}public int sumRange(int left, int right) {int sum=0;for (int i=left;i<=right;i++){sum+=arr[i];}return sum;}}//前缀和
public class NumArray {int[] arr;//前缀和数组public NumArray(int[] nums) {int n=nums.length;arr=new int[n+1];//前缀和数组的arr[0]=0 这样可以避免i=0的特殊判断for (int i=0;i<n;i++){arr[i+1]=arr[i]+nums[i];}}public int sumRange(int left, int right) {//left~right这个区间元素的和是 0~right的前缀和减去0~left-1的前缀和的值return arr[right+1]-arr[left];}}

（2）二维区域和检索 - 矩阵不可变(304)

给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。

//使用一维前缀和
public class NumMatrix {int arr[][];public NumMatrix(int[][] matrix) {int m= matrix.length;//行int n=matrix[0].length;//列arr=new int[m][n+1];for (int i=0;i<m;i++){//计算出每一行的前缀和for (int j=0;j<n;j++){arr[i][j+1]=arr[i][j]+matrix[i][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {int sum=0;for (int i=row1;i<=row2;i++){sum+=arr[i][col2+1]-arr[i][col1];}return sum;}}//使用二维前缀和
public class NumMatrix {int arr[][];public NumMatrix(int[][] matrix) {int m= matrix.length;//行int n=matrix[0].length;//列arr=new int[m+1][n+1];//计算出第一行的所有列的前缀和for (int i=0;i<m;i++){for (int j=0;j<n;j++){arr[i+1][j+1]=arr[i][j+1]+arr[i+1][j]-arr[i][j]+matrix[i][j];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return arr[row2+1][col2+1]-arr[row1][col2+1]-arr[row2+1][col1]+arr[row1][col1];}}

（3）和为 K 的子数组(560)

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。

输入：nums = [1,1,1], k = 2
输出：2输入：nums = [1,2,3], k = 3
输出：2

//暴力枚举
public class Solution {public static void main(String[] args) {int[] arr={1,2,3};int k=3;Solution solution=new Solution();System.out.println(solution.subarraySum(arr,k));}public int subarraySum(int[] nums, int k) {int n= nums.length;int count=0;//连续子数组的个数//依次遍历每个元素 分别以每个元素结尾向前寻找 看能否找到连续子数组的和为kfor (int i=0;i<n;i++){int sum=0;//连续子数组的和for (int j=i;j>=0;j--){sum+=nums[j];if (sum==k){count++;}}}return count;}
}//前缀和+哈希表优化
public class Solution {public static void main(String[] args) {int[] arr={1,2,3};int k=3;Solution solution=new Solution();System.out.println(solution.subarraySum(arr,k));}public int subarraySum(int[] nums, int k) {int n= nums.length;int count=0;//连续子数组的个数int pre=0;//前缀和Map<Integer,Integer> map=new HashMap<>();map.put(pre,1);for (int i=0;i<n;i++){pre+=nums[i];if (map.containsKey(pre-k)){count+=map.get(pre-k);}map.put(pre,map.getOrDefault(pre,0)+1);}return count;}
}

8.练习

（1）重塑矩阵(566)

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

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

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

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

输入：mat = [[1,2],[3,4]], r = 1, c = 4
输出：[[1,2,3,4]]

输入：mat = [[1,2],[3,4]], r = 2, c = 4
输出：[[1,2],[3,4]]

public class Solution {public static void main(String[] args) {int[][] arr={{1,2},{3,4}};int r=1;int c=4;Solution solution=new Solution();int[][] ints = solution.matrixReshape(arr, r, c);System.out.println("行:"+ints.length+"   "+"列:"+ints[0].length);}public int[][] matrixReshape(int[][] mat, int r, int c) {int m= mat.length;int n=mat[0].length;if (r*c!=m*n){return mat;}int[][] arr=new int[r][c];Queue<Integer> queue=new LinkedList<>();//将数组元素入队列for (int i=0;i<m;i++){for (int j=0;j<n;j++){queue.add(mat[i][j]);}}//将队列的元素插入新的数组for (int i=0;i<r;i++){for (int j=0;j<c;j++){arr[i][j]=queue.poll();}}return arr;}
}

（2）用队列实现栈(225)

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

public class MyStack {Queue<Integer> queue;Queue<Integer> auxQueue;//辅助栈public MyStack() {queue=new LinkedList<>();auxQueue=new LinkedList<>();}public void push(int x) {//首先将queue里剩余的元素弹入auxQueue中 为了保证元素顺序while (!queue.isEmpty()){auxQueue.add(queue.poll());}//将auxQueue中元素按照顺序弹入queue中while (!auxQueue.isEmpty()){queue.add(auxQueue.poll());}queue.add(x);}public int pop() {//首先将queue里剩余的元素弹入auxQueue中 为了保证元素顺序while (!queue.isEmpty()){auxQueue.add(queue.poll());}//在每一次操作前 先将auxQueue中的元素弹入queue中while (!auxQueue.isEmpty()){queue.add(auxQueue.poll());}while (queue.size()>1){auxQueue.add(queue.poll());}return queue.poll();}public int top() {//首先将queue里剩余的元素弹入auxQueue中 为了保证元素顺序while (!queue.isEmpty()){auxQueue.add(queue.poll());}//在每一次操作前 先将auxQueue中的元素弹入queue中while (!auxQueue.isEmpty()){queue.add(auxQueue.poll());}while (queue.size()>1){auxQueue.add(queue.poll());}return queue.peek();}public boolean empty() {while (queue.isEmpty()&&auxQueue.isEmpty()){return true;}return false;}
}

（3）下一个更大元素 II(503)

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数； 
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]

//小根堆+循环数组
public class Solution {public static void main(String[] args) {int[] arr={1,2,1};Solution solution=new Solution();int[] ints = solution.nextGreaterElements(arr);for (int i:ints){System.out.print(i+" ");}}public int[] nextGreaterElements(int[] nums) {int n= nums.length;if (n==1){return new int[]{-1};}int[] arr=new int[n];//先将数组中所有位置初始化为-1Arrays.fill(arr,-1);PriorityQueue<int[]> heap=new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {if (o1[0]==o2[0]){return o1[1]-o2[1];}return o1[0]-o2[0];}});for (int i=0;i<n*2-1;i++){//当小根堆不为空并且堆顶元素小于当前元素时 堆顶元素对应位置放当前元素while (!heap.isEmpty()&&heap.peek()[0]<nums[i%n]){arr[heap.poll()[1]]=nums[i%n];}//当前元素入堆heap.add(new int[]{nums[i%n],i%n});}return arr;}
}//单调栈+循环数组
public class Solution {public static void main(String[] args) {int[] arr={1,2,1};Solution solution=new Solution();int[] ints = solution.nextGreaterElements(arr);for (int i:ints){System.out.print(i+" ");}}public int[] nextGreaterElements(int[] nums) {int n= nums.length;if (n==1){return new int[]{-1};}int[] arr=new int[n];//先将数组中所有位置初始化为-1Arrays.fill(arr,-1);//单调栈中保存数组元素下标Deque<Integer> stack=new LinkedList<>();for (int i=0;i<n*2-1;i++){//当栈不为空并且当前元素大于栈顶下标所对应的元素时 将栈顶元素对应位置赋值为当前元素while (!stack.isEmpty()&&nums[stack.peek()]<nums[i%n]){arr[stack.poll()]=nums[i%n];}//当前元素下标入栈stack.push(i%n);}return arr;}
}

（4）存在重复元素(217)

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

输入：nums = [1,2,3,1]
输出：true输入：nums = [1,2,3,4]
输出：false输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

//排序
public class Solution {public static void main(String[] args) {int[] arr={1,2,1};Solution solution=new Solution();System.out.println(solution.containsDuplicate(arr));}public boolean containsDuplicate(int[] nums) {int n=nums.length;if (n==1){return false;}Arrays.sort(nums);for (int i=0;i<n-1;i++){if (nums[i]==nums[i+1]){return true;}}return false;}
}//集合
public class Solution {public static void main(String[] args) {int[] arr={1,2,1};Solution solution=new Solution();System.out.println(solution.containsDuplicate(arr));}public boolean containsDuplicate(int[] nums) {int n=nums.length;if (n==1){return false;}Set<Integer> set=new HashSet<>();for (int i=0;i<n;i++){//当集合中存在某个值时 证明这个值算上当前值至少出现了两次 直接返回trueif (set.contains(nums[i])){return true;}set.add(nums[i]);}return false;}
}

（5）数组的度

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

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

输入：nums = [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 。输入：nums = [1,2,2,3,1,4,2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

//哈希表
public class Solution {public static void main(String[] args) {int[] arr={1,2,2,3,1};Solution solution=new Solution();System.out.println(solution.findShortestSubArray(arr));}public int findShortestSubArray(int[] nums) {int n= nums.length;if (n==1){return 1;}int maxCount=0;//出现最大的频数int minLen=0;//出现频数最多且子数组长度最短的长度//哈希表 用来存储元素 和 其出现的次数以及第一次出现和最后一次出现的位置Map<Integer,int[]> map=new HashMap<>();for (int i=0;i<n;i++){if (map.containsKey(nums[i])){//更新出现的次数已经最后一次出现的位置map.get(nums[i])[0]++;map.get(nums[i])[2]=i;}else {map.put(nums[i],new int[]{1,i,i});}}//依次获取每一个value 比较它们的次数以及对应的子数组的长度 得到答案for (Map.Entry<Integer,int[]> entry:map.entrySet()){int[] arr= entry.getValue();if (maxCount<arr[0]){maxCount=arr[0];//令maxCount=当前频数minLen=arr[2]-arr[1]+1;//更改当前最短子数组长度} else if (maxCount==arr[0]) {minLen=Math.min(minLen,arr[2]-arr[1]+1);}}return minLen;}
}

（6）最长和谐子序列(594)

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]输入：nums = [1,2,3,4]
输出：2输入：nums = [1,1,1,1]
输出：0

//排序
public class Solution {public static void main(String[] args) {int[] arr={1,2,3,4};Solution solution=new Solution();System.out.println(solution.findLHS(arr));}public int findLHS(int[] nums) {int n= nums.length;if (n<2){return 0;}int maxLen=0;//最长和谐子序列的长度Arrays.sort(nums);for (int i=0;i<n-1;i++){int j=i;int preMin=nums[i];//当前和谐子序列最小值//当当前子序列满足和谐子序列时while (j<(n-1)&&(preMin+1)>=nums[j+1]){j++;}//当当前最小值不等于最大值时 才成立if (preMin!=nums[j]){maxLen=Math.max(maxLen,j-i+1);}}return maxLen;}}//哈希表
public class Solution {public static void main(String[] args) {int[] arr={1,2,3,4};Solution solution=new Solution();System.out.println(solution.findLHS(arr));}public int findLHS(int[] nums) {int n= nums.length;if (n<2){return 0;}int maxLen=0;//最长和谐子序列的长度Map<Integer,Integer> map=new HashMap<>();//遍历数组 得到每个元素出现的次数for (int i=0;i<n;i++){if (map.containsKey(nums[i])){map.put(nums[i],map.get(nums[i])+1);}else {map.put(nums[i],1);}}//遍历map 对每一个key值 如果找到key+1也在map里 那么它们对应的和谐子序列长度就是它们的value值相加for (int key:map.keySet()){if (map.containsKey(key+1)){maxLen=Math.max(maxLen,map.get(key)+map.get(key+1));}}return maxLen;}}

（7）寻找重复数(287)

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

输入：nums = [1,3,4,2,2]
输出：2输入：nums = [3,1,3,4,2]
输出：3

public class Solution {public static void main(String[] args) {int[] arr={3,1,3,4,2};Solution solution=new Solution();System.out.println(solution.findDuplicate(arr));}public int findDuplicate(int[] nums) {int n= nums.length;int repeatNum=0;//重复的整数int left=1;int right=n-1;while (left<=right){int mid=(left+right)>>1;int count=0;//计数 来判断重复的数出现在哪for (int i=0;i<n;i++){if (nums[i]<=mid){count++;}}if (count<=mid){left=mid+1;}else {right=mid-1;repeatNum=mid;}}return repeatNum;}}

（8）优势洗牌(870)

给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。

输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]输入：nums1 = [12,24,8,32], nums2 = [13,25,32,11]
输出：[24,32,8,12]

    public int[] advantageCount(int[] nums1, int[] nums2) {int n= nums1.length;int[] arr=new int[n];Integer[] a=new Integer[n];Integer[] b=new Integer[n];int left=0;//数组当前左边界int right=n-1;//数组当前有边界for (int i=0;i<n;i++){a[i]=i;b[i]=i;}//a b 分别来存储 nums1 nums2 排序后的下标值Arrays.sort(a,(i,j)->nums1[i]-nums1[j]);Arrays.sort(b,(i,j)->nums2[i]-nums2[j]);for (int i=0;i<n;i++){//当nums1的当前最小值大于nums2的当前最小值时if (nums1[a[i]]>nums2[b[left]]){arr[b[left]]=nums1[a[i]];left++;}else {arr[b[right]]=nums1[a[i]];right--;}}return arr;}