目錄

最長(zhǎng)連續(xù)序列

解法一：暴力枚舉

復(fù)雜度

解法二：優(yōu)化解法一省去二層循環(huán)中不必要的遍歷

復(fù)雜度

最大子數(shù)組和

解法一：暴力枚舉

復(fù)雜度

解法二：貪心

復(fù)雜度

解法三：動(dòng)態(tài)規(guī)劃

復(fù)雜度

---

最長(zhǎng)連續(xù)序列

輸入輸出示例：

解法一：暴力枚舉

兩層循環(huán)，第一層循環(huán)是遍歷整個(gè)數(shù)組；第二層循環(huán)的目的是得到最長(zhǎng)連續(xù)序列時(shí)間復(fù)雜度極高，效率低下。

1、如果不使用哈希表在枚舉過(guò)程中查找nums[i]+1時(shí)要通過(guò)遍歷整個(gè)數(shù)組來(lái)進(jìn)行，因此時(shí)間復(fù)雜度是O(n^2)

2、使用哈希表枚在舉過(guò)程中雖說(shuō)哈希表查找數(shù)據(jù)的時(shí)間復(fù)雜度是O(1)，但第二次循環(huán)仍然需要執(zhí)行多次，最壞的情況下其時(shí)間復(fù)雜度也會(huì)接近O(n^2)

class Solution {
public:int longestConsecutive(vector<int>& nums) {if(0 == nums.size()) //注意：需要考慮nums為空的情況，此時(shí)的最長(zhǎng)連續(xù)序列就是0return 0;unordered_set<int> hashtable;int max_length = INT_MIN;for(const auto& e:nums) //使用哈希表去重?cái)?shù)據(jù)hashtable.emplace(e);for(const auto& e:hashtable){int tmp = e;int cnt = 1;while(hashtable.count(++tmp))++cnt;max_length = std::max(max_length,cnt);}return max_length;}
};

復(fù)雜度

時(shí)間復(fù)雜度： O(n^2)

空間復(fù)雜度：O(n)

解法二：優(yōu)化解法一省去二層循環(huán)中不必要的遍歷

class Solution {
public:int longestConsecutive(vector<int>& nums) {if(0 == nums.size())return 0;int size = nums.size();int max_length = 0;unordered_set<int> hashtable;for(const auto& e:nums)hashtable.insert(e);for(const auto& e:hashtable){if(!hashtable.count(e-1))//只在哈希表中找連續(xù)序列的第一個(gè)數(shù){int cnt = 1;int tmp = e;while(hashtable.count(++tmp))++cnt;max_length = std::max(max_length,cnt);}}return max_length;}
};

復(fù)雜度

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

最大子數(shù)組和

輸入輸出示例

解法一：暴力枚舉

兩層循環(huán)，定義一個(gè)max_sum變量，第二層循環(huán)中定義一個(gè)tmp變量用來(lái)記錄第二層循環(huán)中連續(xù)子數(shù)組的和。

lass Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();int max_sum = INT_MIN;for(int i = 0;i<size;++i){int tmp = 0; //用來(lái)記錄連續(xù)子數(shù)組的和for(int j = i;j<size;++j){tmp += nums[j];max_sum = std::max(max_sum,tmp);}}return max_sum;}
};

該暴力枚舉會(huì)超出時(shí)間限制，不適合。

復(fù)雜度

時(shí)間復(fù)雜度：O(n^2)

空間復(fù)雜度：O(1)

解法二：貪心

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();int max_sum = nums[0]; //考慮到數(shù)組nums只有一個(gè)元素的時(shí)候，加上題目限制：子數(shù)組中至少包含一個(gè)元素int tmp = nums[0];for(int i = 1;i<size;++i){if(tmp > 0)tmp += nums[i];elsetmp = nums[i];max_sum = std::max(max_sum,tmp);}return max_sum;}
};

復(fù)雜度

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(1)

解法三：動(dòng)態(tài)規(guī)劃

定義一個(gè)dp數(shù)組，dp[i]表示以 i 位置結(jié)尾的子數(shù)組的最大和，利用已經(jīng)有的dp[i-1]值求dp[i]。

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();vector<int> dp(size);//dp[i]表示以i位置結(jié)尾的連續(xù)子數(shù)組的最大和dp[0] = nums[0];int max_sum = dp[0];//當(dāng)size == 1的時(shí)候程序不進(jìn)入下面循環(huán)，直接返回nums[0]for(int i = 1;i<size;++i){if(dp[i-1]>0)dp[i] = dp[i-1] + nums[i];elsedp[i] = nums[i];max_sum = std::max(max_sum,dp[i]);}return max_sum;}
};

復(fù)雜度

時(shí)間復(fù)雜度：O(n)

空間復(fù)雜度：O(n)

使用滾動(dòng)數(shù)組將空間復(fù)雜度優(yōu)化為O(1)：

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();//vector<int> dp(size);//dp[i]表示以i位置結(jié)尾的連續(xù)子數(shù)組的最大和int dp1 = nums[0];int dp2 = 0;int max_sum = dp1;for(int i = 1;i<size;++i){if((dp1+nums[i]) > nums[i])dp2 = dp1 + nums[i];elsedp2 = nums[i];max_sum = std::max(max_sum,dp2);dp1 = dp2;//更新dp1}return max_sum;}
};