代码随想录第二天 |977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II

997有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

解题思路

• 使用头尾双指针的方式

代码演示

 public int[] sortedSquares(int[] nums){
	int left = 0,right = nums.length - 1;
	int[] result = new int[nums.length];
    int index = right;
	while(left <= right){
	   if(nums[left] * nums[left] > nums[right] * nums[right]){
			result[index--] = nums[left] * nums[left];
			left++;
		}else{
			result[index--] = nums[right] * nums[right];
			right--;
		}
	}
	return result; 
}

时间复杂度：O(n)
空间复杂度：O(n)

209.长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

解题思路

滑动窗口的方法

• 一层for循环使用的是终止位置

使用暴力解法

代码演示

暴力解法

       public int minSubArrayLen2(int target, int[] nums) {
      //暴力解法
      int sum = 0;
      int result = Integer.MAX_VALUE;
      int subLength = 0;
      for(int i = 0; i < nums.length; i++){
          sum = 0;
          for(int j = i; j < nums.length; j++){
              sum += nums[j];
              if(sum >= target){
                 subLength = j -i + 1;
                 result = Math.min(result,subLength);
                 break;
              }
          }
      }
      return result == Integer.MAX_VALUE ? 0 : result;
     }

时间复杂度：O(n2)
空间复杂度：O(1)

滑动窗口

public int minSubArrayLen(int target, int[] nums){
	int sum = 0;
	int result = Integer.MAX_VALUE;
	int subLength = 0;
	int i = 0;
	for(int j = 0; j < nums.length; j++){
		sum += nums[j];
		while(sum >= target){
			subLength = j - i + 1;
			result = Math.min(result,sublength);
			sum -= nums[i++];
		}
	}
	return result == Integer.MAX_VALUE ? 0 : result;
}

时间复杂度：O(n)
空间复杂度：O(1)

59.螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

解题思路

• 循环不变量，每一行遍历的遵循一个原则。按照右下左上进行遍历

• 如果是奇数，最后进行判断赋值。

代码演示

public int[][] generateMatrix(int n){
	
	int loop = n/2;
	int mid = n/2;
	int startx = 0;
	int starty = 0;
	int offerSet = 1;
	int i,j;
	int count = 1;
	int[][] result = new int[n][n];
	whilie(loop-- > 0){
		i=startx;
		j=starty;
		
		for(j = starty; j < n - offerSet; j++){
		result[i][j] = count++;
	}
	
		for(i = startx; i < n - offerSet; i++){
		result[i][j] = count++;
	}
	
	for(; j > startx; j--){
		result[i][j] = count++;
	}
		for(; i > starty; i--){
		result[i][j] = count++;
	}
	
	startx++;
	starty++;
	offerSet++;
	}
	if(n % 2 == 1){
		result[mid][mid] = count++;
	}
	return result;
}

时间复杂度：O(n)
空间复杂度：O(n2)