代码随想录——数组篇
- 2. 二分查找
- 3. 移除元素
- 4. 有序数组的平方
- 5. 长度最小的子数组
- 6. 螺旋矩阵II
2. 二分查找
力扣题目链接
前提：
- 有序数组
- 数组中无重复元素
代码：
（版本一）左闭右闭区间
class Solution {
public int search(int[] nums, int target) {
//当 target 小于nums的最小值 或 大于nums的最大值时，直接返回-1
if(target < nums[0] || target > nums[nums.length - 1])
return -1;
int left = 0, right = nums.length - 1, mid;
while(left <= right) {
mid = left + ((right- left) >> 1);
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
}
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
（版本二）左闭右开区间
class Solution {
public int search(int[] nums, int target) {
//当 target 小于nums的最小值 或 大于nums的最大值时，直接返回-1
if(target < nums[0] || target > nums[nums.length - 2])
return -1;
int left = 0, right = nums.length - 1, mid;
while(left < right) {
mid = left + ((right- left) >> 1);
if(nums[mid] == target)
return mid;
else if(nums[mid] > target)
right = mid;
else
left = mid + 1;
}
return -1;
}
}
- 时间复杂度：O(log n)
- 空间复杂度：O(1)
3. 移除元素
力扣题目链接
代码：
双指针法（快慢指针法）
class Solution {
public int removeElement(int[] nums, int val) {
int j = 0;
for(int i = 0; i < nums.length; i++) {
if(nums[i] != val) {
nums[j++] = nums[i];
}
}
return j;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
4. 有序数组的平方
力扣题目链接
前提：
- 非递减顺序 排序的整数数组
思路：
数组本身有序，平方和较大的值一定出现在两端，可以借用前面学习的双指针法。
代码：
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int left = 0, right = nums.length - 1, index = nums.length - 1;
while(left <= right) {
if(nums[left] * nums[left] < nums[right] * nums[right]) {
//大的值从后往前放
result[index--] = nums[right] * nums[right];
right -= 1;
}
else {
result[index--] = nums[left] * nums[left];
left += 1;
}
}
return result;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
5. 长度最小的子数组
力扣题目链接
滑动窗口：
不断调节子序列的起始位置和终止位置，从而得出想要的结果。
滑动窗口三要素：
- 窗口内是什么？
- 满足其和 ≥ target 的长度最小的 连续 子数组。
- 如何移动窗口的起始位置？
- 如果当前窗口的值 ≥ target 了，窗口就要向前移动了（窗口该缩小了）。
- 如何移动窗口的结束位置？
- 窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
代码：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, result = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
//如果滑动窗口内的总和大于或等于target
while(sum >= target) {
//更新最小子序列长度
result = Math.min(result, right - left + 1);
//移动滑动窗口的起始位置，缩小窗口
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
6. 螺旋矩阵II
力扣题目链接
代码：
class Solution {
public static int[][] generateMatrix(int n) {
//定义起始x, y, 偏移量offset
int startX = 0, startY = 0, offset = 1;
//定义移动指针i, j, 圈数loop, 数字num
int i, j, loop = n >> 1, num = 1;
//定义n * n的矩阵
int[][] arr = new int[n][n];
//模拟循环
while((loop--) > 0) {
//从左到右（左闭右开）
for (j = startY; j < n - offset; j++) {
arr[startX][j] = num++;
}
//从上到下（左闭右开）
for (i = startX; i < n - offset; i++) {
arr[i][j] = num++;
}
//从右到左（左闭右开）
for ( ; j > startY; j--) {
arr[i][j] = num++;
}
//从下到上（左闭右开）
for ( ; i > startX; i--) {
arr[i][j] = num++;
}
//一圈结束，起始位置+1，如(0, 0) 变为(1, 1)
startX++;
startY++;
//offset同步更新
offset++;
}
//如果n为奇数，中间的数单独赋值
if(n % 2 == 1)
arr[startX][startY] = num;
return arr;
}
}
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
