目錄

最長連續(xù)序列

解法一：暴力枚舉

復雜度

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

復雜度

最大子數(shù)組和

解法一：暴力枚舉

復雜度

解法二：貪心

復雜度

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

復雜度

---

最長連續(xù)序列

輸入輸出示例：

解法一：暴力枚舉

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

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

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

class Solution {
public:int longestConsecutive(vector<int>& nums) {if(0 == nums.size()) //注意：需要考慮nums為空的情況，此時的最長連續(xù)序列就是0return 0;unordered_set<int> hashtable;int max_length = INT_MIN;for(const auto& e:nums) //使用哈希表去重數(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;}
};

復雜度

時間復雜度： O(n^2)

空間復雜度：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ù)序列的第一個數(shù){int cnt = 1;int tmp = e;while(hashtable.count(++tmp))++cnt;max_length = std::max(max_length,cnt);}}return max_length;}
};

復雜度

時間復雜度：O(n)

空間復雜度：O(n)

最大子數(shù)組和

輸入輸出示例

解法一：暴力枚舉

兩層循環(huán)，定義一個max_sum變量，第二層循環(huán)中定義一個tmp變量用來記錄第二層循環(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; //用來記錄連續(xù)子數(shù)組的和for(int j = i;j<size;++j){tmp += nums[j];max_sum = std::max(max_sum,tmp);}}return max_sum;}
};

該暴力枚舉會超出時間限制，不適合。

復雜度

時間復雜度：O(n^2)

空間復雜度：O(1)

解法二：貪心

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();int max_sum = nums[0]; //考慮到數(shù)組nums只有一個元素的時候，加上題目限制：子數(shù)組中至少包含一個元素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;}
};

復雜度

時間復雜度：O(n)

空間復雜度：O(1)

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

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

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();vector<int> dp(size);//dp[i]表示以i位置結尾的連續(xù)子數(shù)組的最大和dp[0] = nums[0];int max_sum = dp[0];//當size == 1的時候程序不進入下面循環(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;}
};

復雜度

時間復雜度：O(n)

空間復雜度：O(n)

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

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();//vector<int> dp(size);//dp[i]表示以i位置結尾的連續(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;}
};