977.有序數(shù)組的平方??
Given an integer array?nums?sorted in?non-decreasing?order, return?an array of?the squares of each number?sorted in non-decreasing order.
Example 1:
Input:?nums = [-4,-1,0,3,10]
Output:?[0,1,9,16,100]
Explanation:?After squaring, the array becomes [16,1,0,9,100]. After sorting, it becomes [0,1,9,16,100].
#1 自己看到題目的第一想法?
排列題；暴力解法的話就是循環(huán)一遍，得到square的array，即?[16,1,0,9,100]，再用快速排列或者歸并，時(shí)間復(fù)雜度是 nlogn。
另一種方法則是使用雙指針 left 和 right， 取 nums[left]^2 和 nums[right]^2 中大的存入res中，再l++ / r--。
#2 看完代碼隨想錄之后的想法?
本題為什么會考慮到左右指針呢，主要是因?yàn)楸绢}的數(shù)組其實(shí)是有序的，即使是平方之后也是有序的。
同時(shí)，時(shí)間復(fù)雜度為n，比暴力解的nlogn+n還是小很多的。
#3 收獲??
在排序題中，如果本身的數(shù)組是有序的，那么可以選用左右指針而非快排/歸并。
209.長度最小的子數(shù)組??
Given an array of positive integers?nums?and a positive integer?target, return the minimal length of a?contiguous subarray?[numsl, numsl+1, ..., numsr-1, numsr]?of which the sum is greater than or equal to?target. If there is no such subarray, return?0?instead.
Example 1:
Input:?target = 7, nums = [2,3,1,2,4,3]
Output:?2
Explanation:?The subarray [4,3] has the minimal length under the problem constraint.
#1 自己看到題目的第一想法?
暴力解法的話就是 i 從 0 開始，j 從 i 開始，sum i 到 j 的所有元素，看是否大于7，如果大于7，保存 i 到 j 的長度并且停止 j 的循環(huán)。時(shí)間復(fù)雜度為 n^2。
但是在 leetcode 跑也超時(shí)了，那么應(yīng)該怎么降維度呢？
可以使用雙指針降維，如果使用雙指針，left 和 right，left 從 0 開始，right 從 0 開始，res +=?right （res 初始值為 0），如果res >= 7 那么 記錄? (right - left + 1) 并且 l--，否則 r++。
#2 看完代碼隨想錄之后的想法??
本題的雙指針又稱滑動窗口。
移動窗口需要考慮的問題：
- 窗口內(nèi)是什么？
- 如何移動窗口的起始位置？如果窗口內(nèi)大于target了，起始位置移動。
- 如何移動窗口的結(jié)束位置？從起始位置之后移動。
首先要思考 如果用一個(gè)for循環(huán)，那么應(yīng)該表示 滑動窗口的起始位置，還是終止位置。如果只用一個(gè)for循環(huán)來表示 滑動窗口的起始位置，那么如何遍歷剩下的終止位置？此時(shí)難免再次陷入 暴力解法的怪圈。所以 只用一個(gè)for循環(huán)，那么這個(gè)循環(huán)的索引，一定是表示 滑動窗口的終止位置。
#3 收獲? ?
不同于二分搜索， which需要array是有序的，滑動窗口并沒有這個(gè)要求，不是說看到非有序就不能用了，雙指針并沒有這個(gè)限制。同時(shí)，這種做法的?time complexity will be O(N), where ‘N’ is the number of fruits in the input array. The outer for loop runs for all characters, and the inner while loop processes each character only once; therefore, the time complexity of the algorithm will be O(N+N), which is asymptotically equivalent to O(N).
#4 類似題目??
904.水果成籃(opens new window)?和159.?Longest Substring with At Most Two Distinct Characters 也是sliding window解決，一開始用了while來做，感覺會比較messy，用for循環(huán)內(nèi)套 while 反而更加的干凈和簡單。
這兩道 sliding window 都是要求 window 內(nèi)部滿足某種條件，并且 window 中 element 數(shù)量最多/最少。
76.最小覆蓋子串(opens new window)。同上，sliding window的條件是?every character in?t?(including duplicates) is included in the window，需要返回的是最小的 window長度，和前兩道題型幾乎一模一樣。但是本題需要注意的是如何判斷是否包含 t 中的所有元素，這是比較 tricky 的，我一開始試圖暴力循環(huán)但是會超時(shí)。最后解決辦法是用一個(gè)新的變量 missing 來判斷是否全部包含。(438和567 也是類似題）
59.螺旋矩陣II?
Given a positive integer?n, generate an?n x n?matrix?filled with elements from?1?to?n2?in spiral order.
#1 自己看到題目的第一想法?
沒有太大的技術(shù)含量，但是寫起來不容易。
#2 看完代碼隨想錄之后的想法? ?
對于這種問題，一定要首先確認(rèn)左閉右開還是左閉右閉并且在做題過程中牢記這一點(diǎn)就不會越做越亂！
#3 收獲? ??
不加強(qiáng)了左閉右開還是左閉右閉的重要性。
#4 類似題目?
54.?Spiral Matrix
