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

977.有序数组的平方

解题思路

看到这道题的时候，思考题目设定原数组是按照非递减的顺序排列肯定是有意义的，这时思考到，既然是按照非递减的顺序排列，那平方的最大值肯定是在两端，而不会在中间，那这样只要从左到右和从右到左的顺序，将找到的最大值，一个个按照顺序放在新的数组中就好，故想到的解法如下：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];

        int left = 0;
        int right = nums.length-1;
        int index = nums.length-1;
        while(index>=0){
            int leftValue = nums[left]*nums[left];
            int rightValue = nums[right]*nums[right];
            if(leftValue>rightValue){
                result[index] = leftValue;
                left++;
            }else{
                 result[index] = rightValue;
                 right--;
            }
            index--;
        }
        return result;
    }
}

看完解析后的思路

作者和我思路相同，就不再做描述

总结

本质还是双指针的方法，通过左右两个指针，不断的找到双指针范围的最大值，然后去放在对应的数组位置就好

209.长度最小的子数组

解题思路

看到题目后的思路就是两个for循环去遍历获取所有满足条件的区域范围，然后再去找到其中的最小值，所以第一版的代码如下：

public int minSubArrayLen(int target, int[] nums) {
        int minCount = nums.length+1;
        for(int i = 0;i<nums.length;i++){
            int currentCount = 1;
            int j = i+1;
            int value = nums[i];
            while(value<target && j<nums.length){
                value = value+nums[j];
                j++;
                currentCount++;
            }
            if(value>=target){
                if(currentCount==1){
                    return 1;
                }else{
                    if(currentCount<minCount){
                        minCount = currentCount;
                    }
                }
            }

        }
        if(minCount == nums.length+1){
            return 0;
        }
        return minCount;
    }

结果提交后超出了时间限制。当时没想到更好的版本，于是去看了作者的解析思路

看完解析后的思路

利用滑动窗口的思路，通过不断移动起始位置，然后找到该起始位置满足条件的连续区间大小，最后得到最小的区间大小，代码如下：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minCount = Integer.MAX_VALUE;
        int result = 0;
        int left = 0;
        for(int i = 0;i<nums.length;i++){
            result += nums[i];
            while(result>=target){
                minCount = Math.min(i-left+1,minCount);
                result -= nums[left++];
            }
         }
        if(minCount == Integer.MAX_VALUE){
            return 0;
        }
        return minCount;
    }
}

总结

还需要好好思考...

59.螺旋矩阵II

还未做完...待续