LeetCode刷題（十一）-----數組-------medium部分（Java、C++）

162. 尋找峰值

峰值元素是指其值大于左右相鄰值的元素。
給定一個輸入數組nums，其中nums[i] ≠ nums[i+1]，找到峰值元素并傳回其索引。
數組可能包含多個峰值，在這種情況下，傳回任何一個峰值所在位置即可。
你可以假設nums[-1] = nums[n] = -∞。
           

示例 1:

輸入: nums = [1,2,3,1]

輸出: 2

解釋: 3 是峰值元素，你的函數應該傳回其索引 2。

示例 2:

輸入: nums = [1,2,1,3,5,6,4]

輸出: 1 或 5

解釋: 你的函數可以傳回索引 1，其峰值元素為 2；

或者傳回索引 5， 其峰值元素為 6。

說明:你的解法應該是O(logN)時間複雜度的。

思路一：

方法一: 線性掃描

本方法利用了連續的兩個元素 nums[j]和nums[j+1] 不會相等這一事實。于是，我們可以從頭開始周遊 nums數組。每當我們遇到數字 nums[i]，隻需要檢查它是否大于下一個元素nums[i+1]即可判斷 nums[i]是否是峰值。可以通過分别讨論問題的全部三種可能情況來了解本方法的思路。

情況 1. 所有的數字以降序排列。這種情況下，第一個元素即為峰值。我們首先檢查目前元素是否大于下個元素。第一個元素滿足這一條件，是以被正确判斷為峰值。此時，我們不需要繼續向下判斷，也就不會有需要判斷 nums[i] 和上一個元素 nums[i-1]的大小的情況。

情況2.所有的數字以升序排列。這種情況下，我們會一直比較 nums[i]與 nums[i+1]以判斷nums[i]是否是峰值元素。沒有元素符合這一條件，說明處于上坡而非峰值。于是，在結尾，我們傳回末尾元素作為峰值元素，得到正确結果。在這種情況下，我們同樣不需要比較 nums[i]和上一個元素 nums[i-1]，因為處于上坡是nums[i]不是峰值的充分條件。

情況 3. 峰值出現在中間某處。這種情況下，當周遊上升部分時，與情況 2 相同，沒有元素滿足nums[i]>nums[i+1]。我們不需要比較nums[i] 和上一個元素nums[i−1]。當到達峰值元素時，nums[i] > nums[i + 1]條件滿足。此時，我們同樣不需要比較 nums[i]和上一個元素nums[i−1]。這是由于“周遊會到達第i個元素”本身就說明上一個元素（第i- 1個）不滿足 nums[i] > nums[i + 1]這一條件，也就說明nums[i−1]<nums[i]。于是，我們同樣可以得到正确結果。

複雜度分析

時間複雜度 : O(n)。我們對長度為 n的數組 nums隻進行一次周遊。

空間複雜度 : O(1)。隻使用了常數空間。

方法二：遞歸二分查找

算法

我們可以将nums數組中的任何給定序列視為交替的升序和降序序列。通過利用這一點，以及“可以傳回任何一個峰作為結果”的要求，我們可以利用二分查找來找到所需的峰值元素。

在簡單的二分查找中，我們處理的是一個有序數列，并通過在每一步減少搜尋空間來找到所需要的數字。在本例中，我們對二分查找進行一點修改。首先從數組nums中找到中間的元素mid。若該元素恰好位于降序序列或者一個局部下降坡度中（通過将nums[i]與右側比較判斷)，則說明峰值會在本元素的左邊。于是，我們将搜尋空間縮小為 mid的左邊(包括其本身)，并在左側子數組上重複上述過程。

若該元素恰好位于升序序列或者一個局部上升坡度中（通過将 nums[i]與右側比較判斷)，則說明峰值會在本元素的右邊。于是，我們将搜尋空間縮小為 mid的右邊，并在右側子數組上重複上述過程。

就這樣，我們不斷地縮小搜尋空間，直到搜尋空間中隻有一個元素，該元素即為峰值元素。

為了了解本方法的原理，讓我們再次讨論前文提到的全部三種情況。

情況1.這種情況下，首先找到中間元素3。由于它處于下降坡度，将搜尋空間縮小到[1, 2, 3]。對于此子數組，2為中間元素，也處于下降坡度中，于是将搜尋空間縮小到[1, 2]。現在1是中間元素并同樣處于下降坡度，于是将搜尋空間縮小到[1]。最終1作為答案被正确傳回。

情況2.這種情況下，首先找到中間元素3。由于它處于上升坡度，将搜尋空間縮小到[4, 5]。對于此子數組，4為中間元素，也處于上升坡度中，于是将搜尋空間縮小到[5]。最終5作為答案被正确傳回。

情況 3. 這種情況下，峰值位于中間某處。第一個中間元素是 4。它位于上升坡度，表明峰值在其右側。于是，搜尋空間縮小為 [5, 1]。現在，5 位于下降坡度（相對其右側相鄰元素）, 搜尋空間下降為 [5]。于是，5 被正确識别。

複雜度分析

時間複雜度:O(log_2(n))。每一步都将搜尋空間減半。是以，總的搜尋空間隻需要 log_2(n)步。其中 n為 nums數組的長度。

空間複雜度:O(log_2(n))。每一步都将搜尋空間減半。是以，總的搜尋空間隻需要 log_2(n)步。于是，遞歸樹的深度為 log_2(n)。

方法三：疊代二分查找

算法

上述二分查找方法使用了遞歸。我們可以通過疊代達到同樣的效果。本方法即為疊代實作二分查找。

複雜度分析

時間複雜度 : O (log_2(n))。每一步都将搜尋空間減半。是以，總的搜尋空間隻需要 log_2(n)步。其中 n為 nums數組的長度。

空間複雜度 : O(1)。隻使用了常數空間。

作者：LeetCode

連結：https://leetcode-cn.com/problems/find-peak-element/solution/xun-zhao-feng-zhi-by-leetcode/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

我的：

class Solution {
public:
    int findPeakElement(vector<int>& nums) 
    {
        int l = 0;
        int r = nums.size() - 1;
        while(l < r)
        {
            int mid = (l + r)/2;
            if(nums[mid] < nums[mid + 1])
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return l;    
    }
};

           

79. 單詞搜尋

給定一個二維網格和一個單詞，找出該單詞是否存在于網格中。
 單詞必須按照字母順序，通過相鄰的單元格内的字母構成，其中“相鄰”單元格是那些水準相鄰或垂直相鄰的單元格。同一個單   元格内的字母不允許被重複使用。
           

示例:

56.合并區間

給出一個區間的集合，請合并所有重疊的區間。
           

示例1：

輸入: [[1,3],[2,6],[8,10],[15,18]]

輸出: [[1,6],[8,10],[15,18]]

解釋: 區間 [1,3] 和 [2,6] 重疊, 将它們合并為 [1,6].

示例2:

輸入: [[1,4],[4,5]]

輸出: [[1,5]]

解釋: 區間 [1,4] 和 [4,5] 可被視為重疊區間。

思路一：

方法 1：連通塊

直覺

如果我們畫一個圖，區間看成頂點，相交的區間之間連一條無向邊，那麼圖中連通塊内的所有區間都可以合并成一個。

算法

根據上面的直覺，我們可以把圖用鄰接表表示，用兩個方向的有向邊模拟無向邊。然後，為了考慮每個頂點屬于哪個連通塊，我們從任意一個未被通路的節點出發，周遊相鄰點，直到所有頂點都被通路過。為了效率更快，我們将所有通路過的節點記錄在 Set 中，可以在常數時間内查詢和插入。最後，我們考慮每個連通塊，将所有區間合并成一個新的 Interval ，區間左端點 start 是最小的左端點，區間右端點 end 是最大的右端點。

這個算法顯然是正确的，因為這是最暴力的方法。我們對兩兩區間進行比較，是以可以知道他們是否重合。連通塊搜尋的原理是因為兩個區間可能不是直接重合，而是通過第三個區間而間接重合。例如下面的例子：

盡管區間 (1,5) 和 (6, 10) 沒有直接重合，但是任意一個和 (4, 7) 合并之後就可以和另一個産生重合。圖中有兩個連通塊，我們得到如下兩個合并區間：(1, 10) 和 (15, 20)

複雜度分析

• 時間複雜度：O(n^2)

建圖的時間開銷O(V+E)=O(V)+O(E)=O(n)+O(n^2)= O(n^2)，最壞情況所有區間都互相重合，周遊整個圖有相同的開銷，因為 visited 數組保證了每個節點隻會被通路一次。最後每個節點都恰好屬于一個連通塊，是以合并的時間開銷是O(V) = O(n)。總和為：O(n^2) + O(n^2) + O(n) = O(n^2)

• 空間複雜度：O(n^2)

根據之前提到的，最壞情況下每個區間都是互相重合的，是以兩兩區間都會有一條邊，是以記憶體占用量是輸入大小的平方級别。

方法 2：排序

直覺

如果我們按照區間的 start 大小排序，那麼在這個排序的清單中可以合并的區間一定是連續的。

算法

首先，我們将清單按上述方式排序。然後，我們将第一個區間插入merged數組中，然後按順序考慮之後的每個區間：如果目前區間的左端點在前一個區間的右端點之後，那麼他們不會重合，我們可以直接将這個區間插入merged中；否則，他們重合，我們用目前區間的右端點更新前一個區間的右端點end如果前者數值比後者大的話。

一個簡單的證明：假設算法在某些情況下沒能合并兩個本應合并的區間，那麼說明存在這樣的三元組i，j和k以及區間 ints滿足 i < j < k并且 (ints[i],ints[k])可以合并，而(ints[i],ints[j])和(ints[j], ints[k]) 不能合并。這說明滿足下面的不等式：

ints[i].end < ints[j].start

ints[j].end<ints[k].start

ints[i].end≥ints[k].start

我們聯立這些不等式，可以發現沖突：

是以，所有能夠合并的區間必然是連續的。

思路二：

思路:

先按首位置進行排序;

接下來,如何判斷兩個區間是否重疊呢?比如 a = [1,4],b = [2,3]

當 a[1] >= b[0] 說明兩個區間有重疊.

但是如何把這個區間找出來呢?

左邊位置一定是确定，就是 a[0]，而右邊位置是 max(a[1], b[1])

是以,我們就能找出整個區間為:[1,4]

代碼:

作者：powcai

連結：https://leetcode-cn.com/problems/merge-intervals/solution/pai-xu-by-powcai/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

思路三：

這道和之前那道Insert Interval很類似，這次題目要求我們合并區間，之前那題明确了輸入區間集是有序的，而這題沒有，是以我們首先要做的就是給區間集排序，由于我們要排序的是個結構體，是以我們要定義自己的 comparator，才能用 sort 來排序，我們以 start 的值從小到大來排序，排完序我們就可以開始合并了，首先把第一個區間存入結果中，然後從第二個開始周遊區間集，如果結果中最後一個區間和周遊的目前區間無重疊，直接将目前區間存入結果中，如果有重疊，将結果中最後一個區間的 end 值更新為結果中最後一個區間的 end 和目前 end 值之中的較大值，然後繼續周遊區間集，以此類推可以得到最終結果，代碼如下：

解法一:

下面這種解法将起始位置和結束位置分别存到了兩個不同的數組starts 和ends中，然後分别進行排序，之後用兩個指針i和j，初始化時分别指向 starts 和 ends 數組的首位置，然後如果i指向starts 數組中的最後一個位置，或者當 starts 數組上 i+1 位置上的數字大于 ends 數組的i位置上的數時，此時說明區間已經不連續了，我們來看題目中的例子，排序後的 starts 和 ends 為：

starts: 1 2 8 15

ends: 3 6 10 18

紅色為i的位置，藍色為j的位置，那麼此時 starts[i+1] 為8，ends[i] 為6，8大于6，是以此時不連續了，将區間 [starts[j], ends[i]]，即 [1, 6] 加入結果 res 中，然後j指派為 i+1 繼續循環，參見代碼如下：

解法二：

參考連結：

https://www.cnblogs.com/grandyang/p/4370601.html

我的：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        if(intervals.empty())
        {
            return {};
        }
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> res{intervals[0]};
        for(int i = 0; i < intervals.size();++i)
        {
            if(res.back()[1] < intervals[i][0])
            {
                res.push_back(intervals[i]);
            }
            else
            {
                res.back()[1] = max(res.back()[1],intervals[i][1]);
            }
        }
        return res;    
    }
};

           

34. 在排序數組中查找元素的第一個和最後一個位置

給定一個按照升序排列的整數數組nums，和一個目标值target。找出給定目标值在數組中的開始位置和結束位置。
你的算法時間複雜度必須是O(logn) 級别。
如果數組中不存在目标值，傳回[-1,-1]。
           

示例 1:

輸入: nums = [5,7,7,8,8,10], target = 8

輸出: [3,4]

示例 2:

輸入: nums = [5,7,7,8,8,10], target = 6

輸出: [-1,-1]

思路一：

(二分) 時間：O(logn) & 空間：O(1)

解空間具有二分性，起始點為第一個大于等于target的點，若起始點存在，終止點為從第一個大于等于target的點往後最後一個等于target的點。

要注意l + r + 1可能會爆int。

作者：happy_yuxuan

連結：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/leetcode34-zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-s/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

我的：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        if(nums.empty())
        {
            return {-1,-1};
        }
        int l=0;
        int r=nums.size()-1;
        while(l < r)
        {
            int mid = (long long) l + r >> 1;
            if(nums[mid] < target)
            {
                l = mid +1;
            }
            else
            {
                r = mid;
            }
        }
        if(nums[l] != target)
        {
            return {-1,-1};
        }
        int start = l;
        r = nums.size()-1;
        while(l < r)
        {
            int mid = (long long) l + r + 1 >> 1;
            if(nums[mid] == target)
            {
                l = mid;
            }
            else
            {
                r = mid -1;
            }
        }
        return {start,r};  
    }
};

           

54. 螺旋矩陣

給定一個包含m x n個元素的矩陣（m行,n列），請按照順時針螺旋順序，傳回矩陣中的所有元素。
           

示例 1:

輸入:

[

[ 1, 2, 3 ],

[ 4, 5, 6 ],

[ 7, 8, 9 ]

]

輸出: [1,2,3,6,9,8,7,4,5]

示例 2:

輸入:

[

[1, 2, 3, 4],

[5, 6, 7, 8],

[9,10,11,12]

]

輸出: [1,2,3,4,8,12,11,10,9,5,6,7]

思路一：

這裡的方法不需要記錄已經走過的路徑，是以執行用時和記憶體消耗都相對較小

1.首先設定上下左右邊界

2.其次向右移動到最右，此時第一行因為已經使用過了，可以将其從圖中删去，展現在代碼中就是重新定義上邊界

3.判斷若重新定義後，上下邊界交錯，表明螺旋矩陣周遊結束，跳出循環，傳回答案

4.若上下邊界不交錯，則周遊還未結束，接着向下向左向上移動，操作過程與第一，二步同理

5.不斷循環以上步驟，直到某兩條邊界交錯，跳出循環，傳回答案

作者：youlookdeliciousc

連結：https://leetcode-cn.com/problems/spiral-matrix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-3/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

我的：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) 
    {
        vector<int> ans;
        if(matrix.empty())
        {
            return ans;
        }
        int u = 0;
        int d = matrix.size()-1;
        int l = 0;
        int r = matrix[0].size()-1;
        while(true)
        {
            for(int i=l;i<=r;++i)
            {
                ans.push_back(matrix[u][i]);
            }
            if(++u > d)
            {
                break;
            }
            for(int i=u;i<=d;++i)
            {
                ans.push_back(matrix[i][r]);
            }
            if(--r < l)
            {
                break;
            }
            for(int i=r;i >=l;--i)
            {
                ans.push_back(matrix[d][i]);
            }
            if(u > --d)
            {
                break;
            }
            for(int i=d;i>=u;--i)
            {
                ans.push_back(matrix[i][l]);
            }
            if(++l > r)
            {
                break;
            }
        }
        return ans;
    }
};

           

55. 跳躍遊戲

給定一個非負整數數組，你最初位于數組的第一個位置。數組中的每個元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達最後一個位置。
           

示例 1:

輸入: [2,3,1,1,4]

輸出: true

解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然後再從位置 1 跳 3 步到達最後一個位置。

示例 2:

輸入: [3,2,1,0,4]

輸出: false

解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 是以你永遠不可能到達最後一個位置。

思路一：

1.如果某一個作為 起跳點 的格子可以跳躍的距離是 3，那麼表示後面 3 個格子都可以作為 起跳點。

2.可以對每一個能作為 起跳點 的格子都嘗試跳一次，把 能跳到最遠的距離 不斷更新。

3.如果可以一直跳到最後，就成功了。

我的：

class Solution {
public:
    bool canJump(vector<int>& nums) 
    {
        int k = 0;
        for(int i=0;i<nums.size();i++)
        {
            if(i > k)
            {
                return false;
            }
            k = max(k,i+nums[i]);
        }
        return true;    
    }
};

           

33. 搜尋旋轉排序數組

假設按照升序排序的數組在預先未知的某個點上進行了旋轉。(例如，數組[0,1,2,4,5,6,7]可能變為[4,5,6,7,0,1,2])。
搜尋一個給定的目标值，如果數組中存在這個目标值，則傳回它的索引，否則傳回-1。
你可以假設數組中不存在重複的元素。
你的算法時間複雜度必須是O(logn) 級别。
           

示例 1:

輸入: nums = [4,5,6,7,0,1,2], target = 0

輸出: 4

示例 2:

輸入: nums = [4,5,6,7,0,1,2], target = 3

輸出: -1

思路一：

按照我們将整個數組先分為高處和低處，高處在左側，低處在右側，兩者都是遞增的，同時低處的最大值小于高處的最小值，即如圖。

條件劃分

• 由于數組不是單調遞增

• 是以移動左還是移動右要分條件

• 不妨作圖協助分析

• 作圖省略對等号的判斷

分析

已經有了對條件的梳理，我們不妨得出一個結論。

隻要

nums[0] > target

nums[mid] < nums[0]

nums[mid] < target

這三個條件中，符合一個或三個，就移動左點，否則移動右點。

由此可以想到使用異或的方式，來寫代碼。

代碼

作者：jimmy00745

連結：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-er-fen-tiao-jian-de-tiao-jian-shu/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

我的：

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        int l = 0;
        int r = nums.size() - 1;
        int mid;
        while(l < r)
        {
            mid = l +(r - l) / 2;
            if((nums[0]>target)^(nums[mid]<nums[0])^(nums[mid]<target))
            {
                l = mid + 1;
            }
            else
            {
                r = mid;
            }
        }
        return l == r && nums[l] == target? l : -1;    
    }
};

           

152. 乘積最大子序列

給定一個包含n個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重複的三元組。
注意：答案中不可以包含重複的三元組。
           

思路一：

熱身

首先，先找一下它的簡化版 2sum 來熱熱身。

最簡單的想法就是把每兩個都拿出來加一下，看看結果是不是我們想要的。但是直覺告訴我們，這樣子并不高效。舉一個很實際的例子就能明白。

比如這個周末你去參加線下相親會，全場有且隻有兩個人才是真愛。于是我們每個人都要去找其他所有人聊天，去尋找 ta 是不是自己要找的另一半。每個人都要和每個人說話，這樣時間複雜度很高，翻譯成計算機的表示就是 O(n^2)。

怎麼樣可以更高效一點？

這時候要引入哈希表，其實就是一個登記冊，寫上你的名字和你的要求。如果每個人都提前在主持人那裡登記一遍，然後隻要大家依次再報出自己名字，主持人就能夠識别到，ta 就是你要找的人。

2sum 問題最壞的情況是，第一個人和最後一個人配對，每個人都發了一次言。時間複雜度是 O(n)，空間複雜度也是 O(n)，因為主持人要用小本本記錄下每個人的發言，最壞的時候，要把所有人的訴求都記一遍。

three sum

我們先想一個保底的辦法，再去慢慢優化。最簡單的辦法是，每個人都去依次拉上另一個人一起去找第三個人，這個時間複雜度是 O(n3)。

受到上題的啟發，在湊齊兩人以後，他們可以找主持人登記需求的第三人，而不需要在茫茫人海中去找隊友。這樣，我們就把問題優化成了每個人都要找其他每個人，即時間複雜度 O(n2)O(n2)，因為需要主持人記錄資料，這裡還有 O(n)O(n) 的空間複雜度。

再優化

現在已經想到了可用的通用方案，根據題目的特點，看看還有哪裡可以做一些優化。比如提前結束一些不可能的組合。

首先安排所有人按照順序排隊站好，這是一個需要花時間的操作，不過磨刀不誤砍柴工，付出這個時間還是值得的。排序可以做到 O(nlogn)，這是優于 O(n^2)的。

然後我們選擇一個人做C位，既然是C位，那麼就需要左右各有一個人。先選擇隊伍最左邊（最小值）和隊伍最右邊（最大值）兩個人，加上你，算一下總和。如果大于 0，說明實力太強了，就把就把右側的人選調左一位，反之，則調整左邊的人選，增強一下實力。當某邊選到緊挨着你的人的時候，就意味着組隊結束，以你為 C位的所有可能都已經嘗試完畢了。

于是我們開開心心的把解答發到了力扣，然後就得到了一個 WA（wrong answer）。因為力扣的測試用例往往會有很多邊界資料，不針對這些特殊情況做考慮的話，幾乎一定會翻車的。

重構政策

等等，分析到這裡，好像把事情搞得過于複雜了。我們在選擇第一個人的時候就分了三種情況。

重新思考一下，一開始選擇 C 位，實則是為了利用有序數組快速篩選方案。因為這個人位于中間，是以才會有複雜的選取政策。如果第一次直接選擇最左邊的那個人，後面的政策依然類似，以雙指針從最大最小兩端相向而行，直到相遇，或者即将篩選出來三個符号相同的結果，即停止。好像仍然可以找到正确答案，同時也恰好避開了複雜的選 C 位情況。

我們可以進一步把一些明顯出界的條件加上判斷，再一次剪除部分無用嘗試。

作者：wonderful611

連結：https://leetcode-cn.com/problems/3sum/solution/three-sum-ti-jie-by-wonderful611/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

思路二：指針法

連結：https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-gpe3dbjds1/

我的：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        if(nums.size()<3||nums.front()>0||nums.back()<0) return {};
        vector<vector<int>> res;
        for(int i=0;i<nums.size();i++)
        {
            int fix=nums[i];
            if(fix>0) break;
            if(i>0&&fix==nums[i-1])
                continue;
            int l=i+1;
            int r=nums.size()-1;
            while(l<r)
            {
                if(nums[l]+nums[r]==-fix)
                {
                    if(l==i+1 || r==nums.size()-1)
                    {
                        res.push_back(vector<int>{nums[i],nums[l],nums[r]});
                        l++;
                        r--;
                    }
                    else if(nums[l]==nums[l-1])
                        l++;
                    else if(nums[r]==nums[r+1])
                        r--;
                    else
                    {
                        res.push_back(vector<int>{nums[i],nums[l],nums[r]});
                        l++;
                        r--;
                    }
                }
                else if(nums[l]+nums[r]<-fix)
                    l++;
                else r--;
            }
        }
        return res; 
    }
};

           

152. 三數之和

給定一個整數數組nums，找出一個序列中乘積最大的連續子序列（該序列至少包含一個數）。
           

示例 1:

輸入: [2,3,-2,4]

輸出: 6

解釋: 子數組 [2,3] 有最大乘積 6。

示例 2:

輸入: [-2,0,-1]

輸出: 0

解釋: 結果不能為 2, 因為 [-2,-1] 不是子數組。

思路一：

标簽：動态規劃

周遊數組時計算目前最大值，不斷更新

令imax為目前最大值，則目前最大值為 imax = max(imax * nums[i], nums[i])

由于存在負數，那麼會導緻最大的變最小的，最小的變最大的。是以還需要維護目前最小值imin，imin = min(imin * nums[i], nums[i])

當負數出現時則imax與imin進行交換再進行下一步計算

時間複雜度：O(n)

作者：guanpengchn

連結：https://leetcode-cn.com/problems/maximum-product-subarray/solution/hua-jie-suan-fa-152-cheng-ji-zui-da-zi-xu-lie-by-g/

來源：力扣（LeetCode）

著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。

我的：

class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        int max1 = INT_MIN , imax = 1, imin = 1;
        for(int i=0; i<nums.size(); i++){
            if(nums[i] < 0){ 
              int tmp = imax;
              imax = imin;
              imin = tmp;
            }
            imax = max(imax*nums[i], nums[i]);
            imin = min(imin*nums[i], nums[i]);
            
            max1 = max(max1, imax);
        }
        return max1;   
    }
};