977.有序数组的平方
class Solution {
public int[] sortedSquares(int[] nums) {
int[] result = new int[nums.length];
int left = 0;
int right = nums.length - 1;
int idx = nums.length - 1;//result从最后开始
while (left <= right) {
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
result[idx] = nums[left] * nums[left];//如果左边的比右边的大，则left^2，平方值存储在 result 数组中对应的位置
left++;//左边指针向右进1
} else {
result[idx] = nums[right] * nums[right];
right--;
}
idx--;
}
return result;
}
}
//Time Complexity: O(n)
//Space Complexity: O(n)
1. two ponters
209.长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int minLength = Integer.MAX_VALUE;
int left = 0;
int sum = 0;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
}
return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}
}
//time complexity O(n) space complexity O(1).
1. iterate over the nums array using the right pointer 2. use while loop to update the minimum length by comparing it with the current subarray length (right - left + 1)
59. Spiral Matrix II
class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix = new int[n][n];
int num = 1;
int top = 0, bottom = n - 1, left = 0, right = n - 1;
while (num <= n * n) {//Iterate直至填满matrix
//top row from left to right
for (int i = left; i <= right; i++) {
matrix[top][i] = num;
num++;
}
top++;
//最右从上到下
for (int i = top; i <= bottom; i++) {
matrix[i][right] = num;
num++;
}
right--;
if (top <= bottom) {
//bottom 右到左
for (int i = right; i >= left; i--) {
matrix[bottom][i] = num;
num++;
}
bottom--;
}
if (left <= right) {
//最左bottom到top
for (int i = bottom; i >= top; i--) {
matrix[i][left] = num;
num++;
}
left++;
}
}
return matrix;
}
}
//Time/Space Complexity: O(n^2)
//use four pointers (top, bottom, left, right)
