https://leetcode-cn.com/tag/array/
题目汇总
34. 在排序数组中查找元素的第一个和最后一个位置中等
35. 搜索插入位置简单
39. 组合总和中等
40. 组合总和 II中等
41. 缺失的第一个正数困难
42. 接雨水困难
45. 跳跃游戏 II困难
48. 旋转图像中等
53. 最大子序和简单
54. 螺旋矩阵中等
34. 在排序数组中查找元素的第一个和最后一个位置中等
给定一个按照升序排列的整数数组
nums，和一个目标值target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(logn) 级别。如果数组中不存在目标值，返回[-1, -1]。
输入: nums = [5,7,7,8,8,10], target = 8，输出: [3,4]
思路：二分查找
二分查找算法细节详解这位博主写的简直不能太清晰！！！值得一看！！！
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = left_bound(nums, target);
int right = right_bound(nums, target);
return new int[]{left, right};
}
public int left_bound(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 if (nums[mid] == target) {
// 别返回，收缩左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
public int right_bound(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 if (nums[mid] == target) {
// 别返回，收缩右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
}
35. 搜索插入位置简单
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
输入: [1,3,5,6], 5，输出: 2
思路：二分查找
每次根据 nums[mid] 和 target 之间的大小进行判断，相等则直接返回下标，nums[mid] < target 则start右移，nums[mid] > target 则 end 左移
查找结束如果没有相等值则返回 start，该值为插入位置
class Solution {
public int searchInsert(int[] nums, int target) {
if(nums.length==0||nums==null)
return 0;
int start = 0;
int end = nums.length-1;
while(start<=end){
int mid = start+(end-start)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
start = mid + 1;
}
else{
end = mid - 1;
}
}
return start;
}
}
39. 组合总和中等
给定一个无重复元素的数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的数字可以无限制重复被选取。
说明： 所有数字（包括target）都是正整数，解集不能包含重复的组合。
输入: candidates =[2,3,6,7],target =7,所求解集为:
[
[7],
[2,2,3]
]
思路：回溯算法+剪枝
这个解答讲解清楚，点它！！！我何时才能拥有这样的脑子呢，哦我不配
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
int len = candidates.length;
Arrays.sort(candidates);
dfs(candidates, len, target, 0, new ArrayDeque<>(), res);
return res;
}
/**
* @param candidates 数组输入
* @param len 输入数组的长度，冗余变量
* @param residue 剩余数值
* @param begin 本轮搜索的起点下标
* @param path 从根结点到任意结点的路径
* @param res 结果集变量
*/
private void dfs(int[] candidates,
int len,
int residue,
int begin,
Deque<Integer> path,
List<List<Integer>> res) {
if (residue == 0) {
// 由于 path 全局只使用一份，到叶子结点的时候需要做一个拷贝
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 在数组有序的前提下，剪枝
if (residue - candidates[i] < 0) {
break;
}
path.addLast(candidates[i]);
dfs(candidates, len, residue - candidates[i], i, path, res);
path.removeLast();
}
}
}
40. 组合总和 II中等
给定一个数组
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
输入: candidates =[10,1,2,7,6,1,5], target =8,所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
思路：回溯法+剪枝
以 target 为根结点，依次减去数组中的数字，直到小于 0 或者等于 0，把等于 0 的结果记录到结果集中。
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
int len = candidates.length;
Arrays.sort(candidates);
dfs(candidates, len, target, 0, new ArrayDeque<>(), res);
return res;
}
private void dfs(int[] candidates,
int len,
int residue,
int begin,
Deque<Integer> path,
List<List<Integer>> res) {
if (residue == 0) {
// 由于 path 全局只使用一份，到叶子结点的时候需要做一个拷贝
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 在数组有序的前提下，大剪枝
if (residue - candidates[i] < 0) {
break;
}
// 小剪枝，去除重复元素
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
path.addLast(candidates[i]);
dfs(candidates, len, residue - candidates[i], i+1, path, res);
path.removeLast();
}
}
}
41. 缺失的第一个正数困难
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
输入: [1,2,0]，输出: 3
输入: [7,8,9,11,12]，输出: 1
思路：映射哈希+交换
数值为 i 的数映射到下标为 i - 1 的位置上
评论区大佬添加的注释很全面：使用座位交换法
缺失的第一个整数是 [1, len + 1] 之间，那么我们可以遍历数组，然后将对应的数据填充到对应的位置上去，比如 1 就填充到 nums[0] 的位置， 2 就填充到 nums[1]，如果填充过程中， nums[i] < 1 && nums[i] > len，那么直接舍弃。填充完成，我们再遍历一次数组，如果对应的 nums[i] != i + 1，那么这个 i + 1 就是缺失的第一个正数
比如 nums = [7, 8, 9, 10, 11], len = 5
我们发现数组中的元素都无法进行填充，直接舍弃跳过，那么最终遍历数组的时候，我们发现 nums[0] != 0 + 1，即第一个缺失的是 1
比如 nums = [3, 1, 2], len = 3
填充过后，我们发现最终数组变成了 [1, 2, 3]，每个元素都对应了自己的位置，那么第一个缺失的就是 len + 1 == 4
class Solution {
public int firstMissingPositive(int[] nums) {
for(int i=0;i<nums.length;i++){
while(nums[i]>0&&nums[i]<=nums.length&&nums[nums[i]-1]!=nums[i]){
swap(nums,nums[i]-1,i);
}
}
for(int i=0;i<nums.length;i++){
if(nums[i]!=i+1){
return i+1;
}
}
return nums.length+1;
}
public void swap(int[] nums, int index1, int index2){
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
42. 接雨水困难
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]，输出: 6
思路一：暴力法，时间复杂度O(n*n)
对于数组中的每个元素，下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。为了找到最大值每次都要向左和向右扫描一次。
class Solution {
public int trap(int[] height) {
int sum = 0;
for(int i=1;i<height.length-1;i++){
int max_left = 0;
int max_right = 0;
//左边最高列
for(int j=i;j>=0;j--){
if(height[j]>max_left)
max_left = height[j];
}
//右边最高列
for(int j=i;j<height.length;j++){
if(height[j]>max_right)
max_right = height[j];
}
int min = Math.min(max_left,max_right);
//只有较小的一列大于当前列的高度才会有水
if (min > height[i])
sum += (min - height[i]);
}
return sum;
}
}
思路二：动态规划，时间复杂度O(n)
在按列求解的暴力法中，对于每一列，我们求它左边最高的墙和右边最高的墙，都是重新遍历一遍所有高度。为了降低时间复杂度，定义两个数组，max_left [i] 代表第 i 列左边最高的墙的高度，max_right[i] 代表第 i 列右边最高的墙的高度。
class Solution {
public int trap(int[] height) {
int sum = 0;
int[] max_left = new int[height.length];
int[] max_right = new int[height.length];
for(int i = 1; i < height.length - 1; i++){
max_left[i] = Math.max(max_left[i-1],height[i-1]);
}
for(int i = height.length - 2; i >= 0; i--){
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
for (int i = 1; i < height.length - 1; i++) {
int min = Math.min(max_left[i],max_right[i]);
//只有较小的一列大于当前列的高度才会有水
if(min>height[i])
sum += (min - height[i]);
}
return sum;
}
}
45. 跳跃游戏 II困难
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
输入: [2,3,1,1,4]，输出: 2
解释: 跳到最后一个位置的最小跳跃数是2。从下标为 0 跳到下标为 1 的位置，跳1步，然后跳3步到达数组的最后一个位置。
说明:假设你总是可以到达数组的最后一个位置。
思路：贪心算法
搬运解题区精选解题的顺藤摸瓜
class Solution {
public int jump(int[] nums) {
int end = 0;
int maxPosition = 0;
int steps = 0;
for(int i = 0; i < nums.length - 1; i++){
//找能跳的最远的
maxPosition = Math.max(maxPosition, nums[i] + i);
if( i == end){ //遇到边界，就更新边界，并且步数加一
end = maxPosition;
steps++;
}
}
return steps;
}
}
48. 旋转图像中等
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。
说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
思路：转置+翻转，时间复杂度O(n*n)
先转置矩阵，然后翻转每一行
class Solution {
public void rotate(int[][] matrix) {
int len = matrix.length;
//矩阵转置
for(int i=0;i<len;i++){
for(int j=0;j<i;j++){
int temp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = temp;
}
}
//翻转
for(int i=0;i<len;i++){
for(int j=0;j<len/2;j++){
int temp = matrix[i][j];
matrix[i][j] = matrix[i][len-j-1];
matrix[i][len-j-1] = temp;
}
}
}
}
53. 最大子序和简单
给定一个整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4]，输出: 6
解释:连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
思路一：动态规划
首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则需要舍弃，sum 直接更新为当前遍历数字
每次比较 sum 和 ans 的大小，将最大值置为ans，遍历结束返回结果
时间复杂度O(n)
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int i=0;i<nums.length;i++){
if(sum>0){
sum += nums[i];
}
else{
sum = nums[i];
}
ans = Math.max(sum,ans);
}
return ans;
}
}
思路二：分冶法
54. 螺旋矩阵中等
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
与剑指Offer的顺时针打印矩阵相同
思路：设置上下左右四个界限法
定义四个变量代表范围，up、down、left、right
1.向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错
2.向下走存入整列的值，当存入后，该列再也不会被遍历，代表右边界的 right 减一，同时判断是否和代表左边界的 left 交错
3.向左走存入整行的值，当存入后，该行再也不会被遍历，代表下边界的 down 减一，同时判断是否和代表上边界的 up 交错
4.向上走存入整列的值，当存入后，该列再也不会被遍历，代表左边界的 left 加一，同时判断是否和代表右边界的 right 交错
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> list = new ArrayList<>();
if(matrix==null||matrix.length==0||matrix[0].length==0){
return list;
}
int up = 0;//上边界
int down = matrix.length - 1;//下边界，行数-1
int left = 0;//左边界
int right = matrix[0].length - 1;//右边界，列数-1
while(true){
//最上边一行，向右走存入整行的值
for(int col=left;col<=right;col++){
list.add(matrix[up][col]);
}
up++;//向下逼近
if(up>down){
break;
}
//最右边一列，向下走存入整列的值
for(int row=up;row<=down;row++){
list.add(matrix[row][right]);
}
right--;//向左逼近
if(right<left){
break;
}
//最下边一行，向左走存入整行的值
for(int col=right;col>=left;col--){
list.add(matrix[down][col]);
}
down--;//向上逼近
if(down<up){
break;
}
//最左边一列，向上走存入整列的值
for(int row=down;row>=up;row--){
list.add(matrix[row][left]);
}
left++;//向右逼近
if(left>right){
break;
}
}
return list;
}
}
