977.有序數(shù)組的平方

題目描述：
給你一個(gè)按 非遞減順序 排序的整數(shù)數(shù)組 nums让虐，返回 每個(gè)數(shù)字的平方 組成的新數(shù)組，要求也按 非遞減順序 排序罢荡。

示例 1：
輸入：nums = [-4,-1,0,3,10]
輸出：[0,1,9,16,100]
解釋：平方后赡突，數(shù)組變?yōu)?[16,1,0,9,100]
排序后，數(shù)組變?yōu)?[0,1,9,16,100]

題目地址： 有序數(shù)組平方
思路：

• 方法一：暴力解法区赵，也是最容易想到的惭缰，直接數(shù)組的平方，然后對(duì)數(shù)組進(jìn)行排序就行笼才。
• 方法二： 運(yùn)用雙指針法漱受，因?yàn)橛行驍?shù)組存在負(fù)數(shù)，所以最大值一定是在兩邊的骡送，最小值在中間昂羡，我們可以左右指針法，兩邊比較大小摔踱，然后存到新數(shù)組里虐先，最終左右指針碰面循環(huán)結(jié)束（left可以等于right）。

代碼實(shí)現(xiàn)：

vector<int> sortedSquares(vector<int>& nums) {
        if (nums.empty()) {
            return nums;//空數(shù)組直接退出
        }
        vector<int> new_nums(nums.size(), 0);
        int i = 0, j = nums.size() - 1;
        int pingfang1 = 0, pingfang2 = 0;
        int count = j;//用來對(duì)新數(shù)組進(jìn)行賦值
        while(i <= j) {
            pingfang1 = nums[i] * nums[i];
            pingfang2 = nums[j] * nums[j];
            if (pingfang1 <= pingfang2) {
                new_nums[count--] = pingfang2;
                j--;
            } else {
                new_nums[count--] = pingfang1;
                i++;
            }
        }
        return new_nums;
    }

時(shí)間復(fù)雜度：O（n）派敷，空間復(fù)雜度：O（1）

209.長(zhǎng)度最小的子數(shù)組

題目描述：
給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 蛹批。找出該數(shù)組中滿足其總和大于等于 target 的長(zhǎng)度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其長(zhǎng)度篮愉。如果不存在符合條件的子數(shù)組腐芍，返回 0 。

示例 1：
輸入：target = 7, nums = [2,3,1,2,4,3]
輸出：2
解釋：子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的子數(shù)組试躏。

題目鏈接： 長(zhǎng)度最小的子數(shù)組

思路：

• 方法一：暴力解法猪勇，直接使用雙層for循環(huán)，判斷以數(shù)組第一個(gè)元素颠蕴、第二個(gè)元素埠对。络断。。開始的子數(shù)組哪個(gè)符合條件项玛，然后比較出最小子數(shù)組貌笨。復(fù)雜度：O（n^2）

• 方法二：滑動(dòng)窗口法（也是雙指針）〗缶冢快指針去遍歷數(shù)組锥惋，直到走到sum大于target位置時(shí)，移動(dòng)慢指針到剛好sum小于target位置开伏，記錄子數(shù)組長(zhǎng)度膀跌，這樣窗口可以始終保持最小，時(shí)間復(fù)雜度為O（n）固灵；

  
  
  209.長(zhǎng)度最小的子數(shù)組.gif

代碼實(shí)現(xiàn)：

int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;//遍歷數(shù)組時(shí)捅伤，求和
        int i = 0, j = 0;//i為起始位置，j為終止位置巫玻，兩者控制窗口大小
        int sub_result = 0;//改變i時(shí)丛忆，用于存放子數(shù)組大小
        int result = nums.size() + 1; //存放最終結(jié)果，初始值要大于數(shù)組長(zhǎng)度仍秤，最后可以用于判斷是否不存在子數(shù)組
        while(j < nums.size()) {
            sum += nums[j];
            while(sum >= target) {
                sub_result = j - i + 1;
                result = result > sub_result ? sub_result : result;
                sum -= nums[i++];
            }
            j++;
        }
        return result == nums.size() + 1 ? 0 : result;//判斷是不是沒有子數(shù)組符合條件
    }

難點(diǎn)總結(jié)：

• 如何控制窗口大邢ü睢？
  窗口就是 滿足其和 ≥ s 的長(zhǎng)度最小的 連續(xù) 子數(shù)組诗力。
  窗口的起始位置如何移動(dòng)：如果當(dāng)前窗口的值大于s了凰浮，窗口就要向前移動(dòng)了（也就是該縮小了）。
  窗口的結(jié)束位置如何移動(dòng)：窗口的結(jié)束位置就是遍歷數(shù)組的指針苇本，也就是for循環(huán)里的索引袜茧。
  其實(shí)和原地刪除數(shù)組元素的快慢指針類似
• 注意整個(gè)數(shù)組都不符合target的情況

59.螺旋矩陣II

題目描述：
給你一個(gè)正整數(shù) n ，生成一個(gè)包含 1 到 n2 所有元素瓣窄，且元素按順時(shí)針順序螺旋排列的 n x n 正方形矩陣 matrix 惫周。

示例 1：

spiraln.jpeg

輸入：n = 3
輸出：[[1,2,3],[8,9,4],[7,6,5]]
題目鏈接： 59.螺旋矩陣II

難點(diǎn)：

• 如何畫矩陣，畫幾圈康栈、每圈畫幾個(gè)元素（循環(huán)不變量），每次畫邊保持循環(huán)不變量不變喷橙，就不容易出錯(cuò)啥么。

思路：

1. 首先確定要畫幾圈，因?yàn)槊看萎嬕蝗褪莾尚袃闪蟹∮猓灾恍枰?n / 2圈悬荣，n = 3 就畫一圈，n = 4 就畫兩圈
2. 確定每圈的起始位置疙剑，剛開始肯定是（0氯迂，0）践叠，之后每次加1即可。
3. 確定每次畫幾個(gè)元素嚼蚀，其實(shí)只要確定好開頭和結(jié)尾位置就可以了禁灼，以上圖為例，n = 3轿曙， 那么我們就每條邊畫2個(gè)元素（n - 1）弄捕，剛好是一圈，畫第二圈的時(shí)候要畫幾個(gè)元素呢导帝？守谓，因?yàn)橥馊σ呀?jīng)畫了肯定不能是n - 1，此時(shí)我們需要的是n - 2您单， 第3圈就是n - 3斋荞，再看由于外圈畫完少了一圈，所以我們可以加一個(gè)變量用來控制每次畫完一圈后的偏移量offect虐秦，畫第二圈的偏移量就是offect + 1（畫一圈少兩行兩列平酿，offect控制結(jié)束，startx控制開始）
4. 由于當(dāng)n為奇數(shù)的時(shí)候羡疗，中間元素只有一個(gè)染服，不需要畫邊，可以最后單獨(dú)賦值叨恨。

代碼實(shí)現(xiàn)：

vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> nums(n, vector<int>(n, 0));
        int startx = 0, starty = 0;
        int offect = 1; //控制偏移量
        int i = 0, j = 0;
        int count = 1;
        int loop = n / 2; //控制循環(huán)幾圈
        while(loop--) {
            cout << count << " " << startx << " " << starty << endl;
            for (i = startx, j = starty; j < n - offect; ++j) {
                nums[i][j] = count++;
            }
            cout << count << " " << startx << " " << starty << endl;
            for (i = startx, j; i < n - offect; ++i) {
                nums[i][j] = count++;
            }
            for (i, j; j > starty; --j) {
                nums[i][j] = count++;
            }
            for (i,j; i > startx; --i) {
                nums[i][j] = count++;
            }
            startx += 1;//每一圈的起始元素都?1
            starty += 1;
            offect += 1;//用來控制每條邊遍歷的長(zhǎng)度柳刮，因?yàn)椋孔咭蝗ffect - 1
        }

        //當(dāng)n為奇數(shù)時(shí)痒钝，最后一圈為一個(gè)元素秉颗，單獨(dú)賦值,偶數(shù)可以在循環(huán)里賦值
        int mid = n / 2;
        if (n % 2 != 0) {
            nums[mid][mid] = count;
        }
        return nums;
    }

收獲：

• 前兩道題是雙指針法的運(yùn)用，尤其滑動(dòng)窗口法送矩，比較巧妙蚕甥，如何控制窗口大小，開始位置什么時(shí)候變栋荸，結(jié)尾位置怎么控制
• 最后一道題是模擬矩陣菇怀，需要考慮的點(diǎn)比較多，幾圈晌块，每圈的起始位置爱沟，以及保持左閉右開的循環(huán)不變量原則，還有n為奇數(shù)時(shí)要怎么處理匆背。