代码随想录 | Day2 | LC 977有序数组的平方、209长度最小的子数组

977. 有序数组的平方

解法1:暴力

class Solution {
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i <nums.length ; i++) {
            nums[i]=nums[i]*nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

解法2:双指针

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] ints = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int cur = ints.length - 1;
        while (left <= right) {
            int a = nums[left] * nums[left];
            int b = nums[right] * nums[right];
            if (a <= b) {
                ints[cur] = b;
                right--;
            }
            else {
                left++;
                ints[cur] = a;
            }
            cur--;
        }
        return ints;
    }
}

解法2小总结:

209. 长度最小的子数组

解法1：暴力（两层for循环遍历）

​ (测试用例可过,但超时)

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int size = Integer.MAX_VALUE;//表示最短子数组的长度,赋予其int型参数的最大值

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return 1;
            }
            int sum = nums[i];//这个sum一定是写在第一层for内,第二层for外的,统计每次for循时的子数组累加值
            for (int j = i + 1; j < nums.length; j++) {//j用于比较当前i下标的后一个元素,故其下标是从i+1开始往后比
                sum += nums[j];
                int cur_zi_length = j - i + 1;////j-i+1表示的是(j-i)下标差值,再加1(数组下标从零开始),其是当前子数组的长度
                if (sum >= target) {
                    size = Math.min(size, cur_zi_length);
                    break;
                }
            }
        }

        return size == Integer.MAX_VALUE ? 0 : size;
    }
}

解法2：滑动窗口

​ （重要，字符串类题型经典解法）

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0, left = 0, right = 0;
        int size = Integer.MAX_VALUE;//窗口开始size是0,故左右指针均为00;
        while (right < nums.length) {//right向右滑动,直至数组的最后一个元素
            sum += nums[right];
            while (sum >= target) {
                int zi_length = right - left + 1;//当前再遍历的子串的长度
                size = Math.min(zi_length, size);
                sum -= nums[left];
                left++;//窗口左边右缩,是在缩减值,寻找最短子串
            }
            right++;
            //没有找到符合目标值的,就右扩,将当前窗口扩大,正整数数组的原因,sum累计值一定会变大
        }
        return size == Integer.MAX_VALUE ? 0 :size;
        //若没进内while,则还是为原本的最大值,;若进去了,则会返回我们的目标size
    }
}

解法2小总结

59. 螺旋矩阵 II

(挖坑^_)