算法练习第二天 977|209

977 有序数组的平方

思路：这题最简单的做法就是将每个元素都平方后再进行排序

1.暴力解法

代码如下：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            nums[i] = nums[i] * nums[i];
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

时间复杂度O(n + )

2.双指针算法

由于原数组本身就是升序的数组，所以平方后只有可能出现数组两端的元素排序不正确，那么我们可以定义一个新数组和左右两个指针，比较两边的元素平方后的大小将其放入新数组

代码如下：

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int k = nums.size() - 1;
        vector<int> res(nums.size(), 0);
        for(int i = 0, j = nums.size() - 1; i <= j;){
            if(nums[i] * nums[i] < nums[j] * nums[j]){
                res[k--] = nums[j] * nums[j];
                j--;
            }else{
                res[k--] = nums[i] * nums[i];
                i++;
            }
        }
        return res;
    }
};

时间复杂度O(n)

209 长度最小的子数组

思路：这题第一眼看就可以用暴力解法去解决，复杂度是 明显会TLE，所以我们要想其他办法，这里我们用滑动窗口来解决这个问题，我们用两个指针来代表子数组的起始位置和终止位置，当窗口的和满足条件时，我们记录窗口的长度

1.滑动窗口

代码如下：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int ans = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while(end < nums.size()){
            sum += nums[end];
            while(sum >= target){
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INT_MAX ? 0 : ans; 
    }
};

时间复杂度为O(n)