大家好， 一个刷题困难户，接下来我们开始数组类型算法的刷题之旅！
数组基本上是我们最熟悉的数据结构了，刚会写“Hello World”不久，接着就是“杨辉三角”之类的练习。
上图是一个字符数组的例子。
因为内存空间连续，所以可以直接通过下标获取对应的元素。
但是删除就麻烦一点，相当于填坑，一个元素被移走，留下的坑，需要其它元素来填上。
在Java中，多维数组的存储本质上也是一个行优先的一维数组。
我们都知道，在Java中的 “=” 用在基本数据类型上，是值传递，用在引用数据类型上，是引用传递。
这一块展开可以写一篇文章，我们只简单看个例子：
public class ArrayTest {
public static void main(String[] args) {
int[] array = {1, 2, 3};
int[] newArray = array;
newArray[1] = 0;
//结果：1 0 3
printArray(array);
//结果：1 0 3
printArray(newArray);
}
static void printArray(int[] data) {
for (int d : data) {
System.out.print(d + " ");
}
System.out.println();
}
}大家可以看到，newArray改变了，array也跟着变了。
为什么呢？
在Java中，数组是引用数组类型。array、newArray都是存储在栈中的引用，它们指向堆中真正存储的数组对象。
所以改变了newArray，实际是改变了newArray指向的数组。
这一点是我们刷题需要注意的，复制数组需要在循环中一个个复制。
❝好了，接下来，让我们愉快地开始刷题吧！
❞
☕ 题目：704. 二分查找 (https://leetcode-cn.com/problems/binary-search/)
❓ 难度：简单
描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
思路：
二分查找可以说我们都很熟了。
因为数组是有序的，所以定义三个指针，low、high、mid，每次与中间指针指向的元素nums[mid]比较，
/**
* 704. 二分查找
*
* @param nums
* @param target
* @return
*/
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
//target在(mid,high]区间
//右移
left = mid + 1;
} else if (target < nums[mid]) {
//target 在[low,mid)区间
//左移
right = mid - 1;
}
}
return -1;
}但是这个代码还有一处问题，在哪呢？
int mid = (left + right) / 2;
这个地方可能会因为left和right数值太大导致内存溢出，所以应该写为int mid = left + ((right - left) >> 1);
修改之后代码如下：
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid=left+((right-left)>>1);
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
//target在(mid,high]区间
//右移
left = mid + 1;
} else if (target < nums[mid]) {
//target 在[low,mid)区间
//左移
right = mid - 1;
}
}
return -1;
}⏰ 时间复杂度：O(logn)
☕ 题目：35. 搜索插入位置 (https://leetcode-cn.com/problems/search-insert-position/)
❓ 难度：简单
描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
思路：
二分查找比较简单，但写对还要费点功夫，再做一道基本一样的题巩固一下。
这道题基本一样，插入的位置可能有四种情况：
代码如下：
/**
* 35. 搜索插入位置
*
* @param nums
* @param target
* @return
*/
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
//target小于最左侧，或者大于最右元素
if (target < nums[left]) {
return 0;
}
if (target > nums[right]) {
return right + 1;
}
while (left <= right) {
int mid=left+((right-left)>>1);
if (target == nums[mid]) {
//和数组元素相等
return mid;
} else if (target > nums[mid]) {
//右侧
left = mid + 1;
} else if ((target < nums[mid])) {
//左侧
right = mid - 1;
}
}
// 在某个元素之后插入
//因为退出条件是left==right，所以返回left或者right都可以
return left;
}⏰ 时间复杂度：O(logn)
☕ 题目：34. 在排序数组中查找元素的第一个和最后一个位置 (https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)
❓ 难度：中等
描述：
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
思路：
看到时间复杂度 O(log n) ，数组有序，我们知道，二分查找该上场了。
但是这道题有点不一样，它需要寻找边界。
那我们怎么办呢？
这就引入了寻找边界的二分查找。
这道题的思路是什么呢？
我们分别用二分查找来寻找左边界和右边界。
一般的二分查找：
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
left = mid + 1;
}else if (nums[mid] > target) {
right = mid - 1;
}注意，我们这里的返回条件是 nums[mid] == target，但是寻找边界的时候就不能这样了，因为我们不能确定mid是不是我们的边界。
以寻找左边界为例，条件是 target <= nums[mid]的时候，我们接着往左移动。
寻找右边界也类似。
代码如下：
public int[] searchRange(int[] nums, int target) {
//左边界
int leftBound = leftBound(nums, target);
//右边界
int rightBound = rightBound(nums, target);
//不存在情况
if (rightBound < leftBound) {
return new int[]{-1, -1};
}
return new int[]{leftBound, rightBound};
}
/**
* @return int
* @Description: 求左边界
*/
int leftBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
//往左移动
if (target <= nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
//向右移动
left = mid + 1;
}
}
return left;
}
/**
* @return int
* @Description: 求右边界
*/
int rightBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
//往右移动
if (target >= nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
//往左移动
right = mid - 1;
}
}
return right;
}⏰ 时间复杂度：O(logn)
☕ 题目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)
❓ 难度：简单
描述：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}思路
「暴力解法」
暴力解法没什么好说的，和上道题类似，找到要删除的元素，把它后面的元素全部向前移动一位。
这里有两点需要注意：
代码如下：
public int removeElement(int[] nums, int val) {
int length = nums.length;
int i = 0;
for (; i < length; i++) {
if (nums[i] == val) {
for (int j = i; j < length - 1; j++) {
nums[j] = nums[j + 1];
}
//防止漏删
i--;
//数组长度减一
length--;
}
}
return length;
}⏰ 时间复杂度：O(n²)。
「双指针法」
双指针法，是数组和链表题中非常常用的一种方法。
这道题用双指针法怎么解决呢？
定义两个指针，一个前，一个后。没有找到目标的时候front和after一起移动，找到目标的时候，after停下来，front接着移动，把front指向的值赋给after指向的值。
这样一来，双指针就通过一个循环完成了双循环完成的事情。
代码如下：
public int removeElement(int[] nums, int val) {
//定义前后指针
int front = 0;
int after = 0;
for (; front < nums.length; front++) {
if (val != nums[front]) {
nums[after] = nums[front];
after++;
}
}
return after;
}⏰ 时间复杂度：O(n)。
☕ 题目：27. 移除元素 (https://leetcode-cn.com/problems/remove-element/)
❓ 难度：简单
描述：
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
思路
趁着上一道题劲儿还没缓过来，赶紧做一道基本一样的巩固一下。
直接上代码：
public int removeDuplicates(int[] nums) {
int front = 1;
int after = 1;
for (; front < nums.length; front++) {
if (nums[front] != nums[front - 1]) {
nums[after] = nums[front];
after++;
}
}
return after;
}⏰ 时间复杂度：O(n)。
☕ 题目：283. 移动零 (https://leetcode-cn.com/problems/move-zeroes/)
❓ 难度：简单
描述：
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
「示例:」
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]「说明」:
思路
继续沿着上一道题的思路。
代码如下：
/**
* @return void
* @Description: 283. 移动零
* @author 三分恶
* @date 2021/7/30 7:44
*/
public void moveZeroes(int[] nums) {
int after = 0;
int front = 0;
//移动元素
for (; front < nums.length; front++) {
if (nums[front] != 0) {
nums[after] = nums[front];
after++;
}
}
//将末尾元素置为0
for (; after < nums.length; after++) {
nums[after] = 0;
}
}⏰ 时间复杂度：O(n)。
☕ 题目：977. 有序数组的平方 (https://leetcode-cn.com/problems/squares-of-a-sorted-array/)
❓ 难度：简单
描述：
给你一个按 「非递减顺序」 排序的整数数组 nums，返回 「每个数字的平方」 组成的新数组，要求也按 「非递减顺序」 排序。
思路
「暴力排序法」
这道题一看，最直观的做法是什么呢？
先求数字平方的数组，然后再把新数组排序。
代码也好写：
/**
* @return int[]
* @Description: 977. 有序数组的平方-暴力法
* @author 三分恶
* @date 2021/7/30 8:03
*/
public int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] *= nums[i];
}
//快排，时间复杂度O(nlogn)
Arrays.sort(nums);
return nums;
}⏰ 时间复杂度：遍历时间复杂度O(n)，快排时间复杂度O(nlogn)，所以时间复杂度O(n+nlogn)。
思路
「双指针法」
我们连写几道双指针了，这道题能不能用双指针实现呢？
我们分析一下，这个数组在取平方之前，是有序的，那么它绝对值最大的数一定是在两端的。
所以我们可以定义两个指针，一个指向最左端，一个指向最右端，比较两者平方的大小，大的平方放入结果数组，并移动指针。
代码如下：
/**
* @return int[]
* @Description: 977. 有序数组的平方-双指针法
* @author 三分恶
* @date 2021/7/30 8:29
*/
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] result = new int[nums.length];
int r = nums.length - 1;
while (left <= right) {
int leftRes = nums[left] * nums[left];
int rightRes = nums[right] * nums[right];
//右边大
if (leftRes <= rightRes) {
result[r] = rightRes;
right--;
} else {
//左边大
result[r] = leftRes;
left++;
}
r--;
}
return result;
}⏰ 时间复杂度：O(n)。
☕ 题目：1. 两数之和 (https://leetcode-cn.com/problems/two-sum/)
❓ 难度：简单
描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路：
「暴力解法」
上来我们先来个最简单的暴力解法，大家应该都知道冒泡排序吧，类似的两层循环。
代码写起来也很简单：
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}⏰ 时间复杂度：看到这个双循环，就知道时间复杂度O(n²)。
「哈希辅助法」
时间复杂度O(n²)多少有点过了，这道题的重点是两个元素相加之和的判断。
我们可以用一个Hash集合把元素存起来，这样一来遍历一遍就够了，例如目标和9，当前元素2，只需要判断集合里是否有元素7就行了。
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>(16);
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
//目标元素
int goal = target - nums[i];
if (map.containsKey(goal)) {
result[0] = map.get(goal);
result[1] = i;
return result;
}
//将数组值作为key,下标作为value
map.put(nums[i], i);
}
return result;
}⏰ 时间复杂度：从Hash查询和取值时间复杂度都是O(1)，所以整体时间复杂度是O(1)。
☕ 题目：15. 三数之和 (https://leetcode-cn.com/problems/3sum/)
❓ 难度：简单
描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
思路：
「哈希法」
做完两数之和以后，我们首先想到的就是哈希法。
两层循环，取到a，b，再通过 0-(a+b) 来确定c。
但是这里还有一个问题，答案中不可以包含重复的三元组。
所以，我们还要想办法去掉Hash里的重复元素。
可以加入一个约束，第三个数的索引大于第二个数才存入。
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 3) {
return result;
}
//排序
Arrays.sort(nums);
HashMap<Integer, Integer> map = new HashMap<>();
//将元素存入hash表
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
Integer c;
int target = 0;
for (int a = 0; a < nums.length; a++) {
target = -nums[a];
//去重
if (a > 0 && nums[a] == nums[a - 1]) {
continue;
}
for (int b = a + 1; b < nums.length; b++) {
//去重
if (b > a + 1 && nums[b] == nums[b - 1]) {
continue;
}
//从hash表获取c
if ((c = map.get(target - nums[b])) != null) {
//c下彪必须大于b
if (c > b) {
result.add(new ArrayList<>(Arrays.asList(nums[a], nums[b], nums[c])));
} else {
break;
}
}
}
}
return result;
}⏰ 时间复杂度：双循环，O(n²)。
虽然这么也写出来了，但是，说实话，很难写出没有问题的代码。
我们写了这么多双指针，那么有没有可能用双指针的方式呢？
「双指针法」
首先对数组进行排序，然后遍历数组。
然后再在当前节点后面取左右指针，判断左右指针的值是否等于0-nums[i]，然后分别左右移动。
怎么去重呢？
满足条件时，看左指针的值是否和前一个位置相等，右指针的值是否和和它后一个位置的值相等。
代码如下：
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 3) {
return result;
}
//排序
Arrays.sort(nums);
//遍历
for (int i = 0; i < nums.length-2; i++) {
//如果当前元素大于0，三数之和一定大于0
if (nums[i] > 0) {
break;
}
int left = i + 1;
int right = nums.length - 1;
int count = 0 - nums[i];
//去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
//去重,注意去重逻辑要放在找到第一个三元组之后
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
//找到结果，双指针同时移动
left++;
right--;
} else if (sum < 0) {
//左指针右移
left++;
} else if (sum > 0) {
//右指针左移
right--;
}
}
}
return result;
}⏰ 时间复杂度：O(n²)
☕ 题目：18. 四数之和 (https://leetcode-cn.com/problems/4sum/)
❓ 难度：简单
描述：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
思路：
我们延续三数之和的思路，在三数之和外面再套一层循环。
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 4) {
return result;
}
//排序
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
//去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length - 2; j++) {
//去重
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
//去重
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum > target) {
right--;
} else if (sum < target) {
left++;
}
}
}
}
return result;
}⏰ 时间复杂度：O(n³)
☕ 题目：209. 长度最小的子数组(https://leetcode-cn.com/problems/minimum-size-subarray-sum/)
❓ 难度：中等
描述：
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路
这道题是一道经典的滑动窗口问题[4]。
代码如下：
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
//起、止指针
int start = 0, end = 0;
//总和
int sum = 0;
while (end < nums.length) {
//sum添加，end右移
sum += nums[end++];
while (sum >= target && start < end) {
//因为end++，所以序列长度end - start
result = Math.min(result, end - start);
//移动start
sum -= nums[start++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}⏰ 时间复杂度：O(n)，虽然循环里套循环了，但是starrt和end各自被移动了n次，所以时间复杂度是O(n)。
☕ 题目：219. 存在重复元素 II (https://leetcode-cn.com/problems/contains-duplicate-ii/)
❓ 难度：简单
描述：
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
思路：
上面我们做了一道滑动窗口的题，我们接着再做一道也可以用滑动窗口解决的问题。
这道题的滑动窗口略有区别，上一道题的窗口是活动的，这个是固定的滑动窗口,维护一个长度为k的固定窗口，如果窗口内含有目标值，返回。如果窗口进入新的元素，就需要把头部的元素移除掉，保持窗口的长度。
代码如下：
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}⏰ 时间复杂度：O(n)。
☕ 题目：1052. 爱生气的书店老板(https://leetcode-cn.com/problems/grumpy-bookstore-owner/)
❓ 难度：中等
描述：
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意。
「示例：」
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.思路：
这道题是一道固定窗口的问题。
整体思路就是把不生气的部分作为固定窗口，固定窗口把customers分成了三部分，最后求三部分的最大和。
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
// 窗口值总和
int winSum = 0;
//左区间总和
int leftSum = 0;
//右区间总和
int rightSum = 0;
int len = customers.length;
//窗口位于起点
for (int i = 0; i < minutes; i++) {
winSum += customers[i];
}
//窗口位于起点时右区间的值
for (int i = minutes; i < len; i++) {
//不生气
if (grumpy[i] == 0) {
rightSum += customers[i];
}
}
//窗口左右-开始移动窗口
int left = 1;
int right = minutes;
int maxSum = winSum + leftSum + rightSum;
//移动
while (right < len) {
//重新计算左区间的值
if (grumpy[left - 1] == 0) {
leftSum += customers[left - 1];
}
//重新计算右区间的值
if (grumpy[right] == 0) {
rightSum -= customers[right];
}
//窗口值
winSum = winSum - customers[left - 1] + customers[right];
//最大总和
maxSum = Math.max(maxSum, leftSum + winSum + rightSum);
//移动固定窗口
left++;
right++;
}
return maxSum;
}⏰ 时间复杂度：O(n)。
空间复杂度：O(1)。
☕ 题目：面试题3. 数组中重复的数字 (https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)
❓ 难度：复杂
描述：
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
「示例 1：」
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3思路：
「哈希法」
这种找重复的数字问题，我们脑子里第一下就想起来，用Hash存储元素，然后进行比对。
代码实现也很简单：
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
return nums[i];
}
set.add(nums[i]);
}
return 0;
}⏰ 时间复杂度：O(n)。
空间复杂度：O(n)
但今天的主角不是它，而是
「原地置换法」
我们注意到一个条件所有数字都在 0～n-1 的范围内,那就在这方面进行操作，我们可以把元素放到它的值对应的下标的位置。
例如 num[2]=1，那我们就把它放到下标1的位置。
接着遍历，元素发现它应该待的坑已经被它的双胞胎兄弟给占了，它就知道，它是多余的那个。
代码如下：
public int findRepeatNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
for (int i = 0; i < nums.length; i++) {
while (nums[i] != i) {
//判断位置是否被占
int index = nums[i];
if (nums[index] == nums[i]) {
return nums[i];
}
//交换位置
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
}
return -1;
}⏰ 时间复杂度：O(n)。
空间复杂度：O(1)
☕ 题目：41. 缺失的第一个正数 (https://leetcode-cn.com/problems/first-missing-positive/)
❓ 难度：复杂
描述：
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
思路
「辅助数组」
这道题有一个非常巧妙地的办法！[1]
可以引入一个辅助数组，从1开始，在对应的位置存入原数组对应的元素。如原数组num[0]=1，那么这个元素就应该存入辅助数组 helper[1]。
然后遍历辅助数组，发现的第一个坑就是缺失的第一个正数。
代码如下：
public int firstMissingPositive(int[] nums) {
if (nums.length == 0) {
return 1;
}
//辅助数组
int[] helper = new int[nums.length + 1];
//将数组正数元素存入辅助数组中
for (int n : nums) {
if (n > 0 && n < helper.length) {
helper[n] = n;
}
}
//遍历查找，找到不一样元素
for (int i = 1; i < helper.length; i++) {
if (helper[i] != i) {
return i;
}
}
return helper.length;
}⏰ 时间复杂度：O(n)。
空间复杂度：O(n)。
「原地置换法」
我们上面用了原地置换法解决了一个问题，降低了空间复杂度，我们这道题是不是也可以呢？
原地置换没法修改数组长度，我们肯定不能nums[i] 存 i 了，我们左移一下，num[i-1]存i。
代码实现如下：
public int firstMissingPositive(int[] nums) {
if (nums.length == 0) {
return 1;
}
//原地置换
for (int i = 0; i < nums.length; i++) {
//将正数填入对应位置
//需要考虑指针移动情况，大于0，小于len+1，不等与i+1，两个交换的数相等时，防止死循环
while (nums[i] > 0 && nums[i] < nums.length + 1 && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
//下标
int index = nums[i] - 1;
//交换
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
}
}
//遍历置换后的数组
for (int j = 0; j < nums.length; j++) {
if (nums[j] != j + 1) {
return j + 1;
}
}
return nums.length + 1;
}⏰ 时间复杂度：O(n)。
空间复杂度：O(1)。
☕ 题目：54. 螺旋矩阵 (https://leetcode-cn.com/problems/spiral-matrix/)
❓ 难度：中等
描述：
给你一个 m 行 n 列的矩阵 matrix ，请按照 「顺时针螺旋顺序」 ，返回矩阵中的所有元素。
思路
这道题，思路比较容易想，就是上右下左四个方向顺时针遍历数组。
但是这道题的细节是魔鬼。
有两种，一种是一圈遍历完成，上下左右的位置移动，遍历是左闭右开[的条件。
我们采用的是第二种，每遍历完一条边，就移动对应的位置，遍历就是左闭右闭的条件。
还有一点细节就是值得注意的是，遍历过程中可能会出现出现 top > bottom || left > right ，其中一对边界彼此交错了。
这意味着此时所有项都遍历完了，如果没有及时 break ，就会重复遍历。
代码如下：
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>(16);
//边界
int left = 0, right = matrix[0].length - 1;
int top = 0, bottom = matrix.length - 1;
int size = matrix.length * matrix[0].length;
//遍历
while (result.size() != size) {
//上层遍历
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++;
if (top > bottom) break;
//右层遍历
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--;
if (left > right) break;
//下层遍历
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--;
if (top > bottom) break;
//左层遍历
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++;
if (left > right) break;
}
return result;
}时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。
☕ 题目：59. 螺旋矩阵 II (https://leetcode-cn.com/problems/spiral-matrix-ii/)
❓ 难度：中等
描述：
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思路
和上面一道题基本一模一样，我们往里面套就行了。
代码如下：
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int left = 0, right = n - 1;
int top = 0, bottom = n - 1;
int x = 1;
while (x <= n * n) {
//上
for (int i = left; i <= right; i++) {
res[top][i] = x;
x++;
}
top++;
if (top > bottom) break;
//右
for (int i = top; i <= bottom; i++) {
res[i][right] = x;
x++;
}
right--;
if (left > right) break;
//下
for (int i = right; i >= left; i--) {
res[bottom][i] = x;
x++;
}
bottom--;
if (left > right) break;
//左
for (int i = bottom; i >= top; i--) {
res[i][left] = x;
x++;
}
left++;
if (left > right) break;
}
return res;
}时间复杂度：O(n²)
剑指 Offer 29. 顺时针打印矩阵 也是一道类似的题目。
写了个顺口溜总结一下：
❝简单事情重复做，重复事情认真做，认真事情创造性地做！
参考：
本文由哈喽比特于2年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/g-d9dO8XJZjDujBBcGn-cA
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
