【leetcode|哈希表、动态规划】最长连续序列、最大子数组和

目录

最长连续序列

解法一：暴力枚举

复杂度

解法二：优化解法一省去二层循环中不必要的遍历

复杂度

最大子数组和

解法一：暴力枚举

复杂度

解法二：贪心

复杂度

解法三：动态规划

复杂度

---

最长连续序列

输入输出示例：

解法一：暴力枚举

两层循环，第一层循环是遍历整个数组；第二层循环的目的是得到最长连续序列时间复杂度极高，效率低下。

1、如果不使用哈希表在枚举过程中查找nums[i]+1时要通过遍历整个数组来进行，因此时间复杂度是O(n^2)

2、使用哈希表枚在举过程中虽说哈希表查找数据的时间复杂度是O(1)，但第二次循环仍然需要执行多次，最坏的情况下其时间复杂度也会接近O(n^2)

class Solution {
public:int longestConsecutive(vector<int>& nums) {if(0 == nums.size()) //注意：需要考虑nums为空的情况，此时的最长连续序列就是0return 0;unordered_set<int> hashtable;int max_length = INT_MIN;for(const auto& e:nums) //使用哈希表去重数据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)

解法二：优化解法一省去二层循环中不必要的遍历

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))//只在哈希表中找连续序列的第一个数{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)

最大子数组和

输入输出示例

解法一：暴力枚举

两层循环，定义一个max_sum变量，第二层循环中定义一个tmp变量用来记录第二层循环中连续子数组的和。

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; //用来记录连续子数组的和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]; //考虑到数组nums只有一个元素的时候，加上题目限制：子数组中至少包含一个元素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)

解法三：动态规划

定义一个dp数组，dp[i]表示以 i 位置结尾的子数组的最大和，利用已经有的dp[i-1]值求dp[i]。

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();vector<int> dp(size);//dp[i]表示以i位置结尾的连续子数组的最大和dp[0] = nums[0];int max_sum = dp[0];//当size == 1的时候程序不进入下面循环，直接返回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)

使用滚动数组将空间复杂度优化为O(1)：

class Solution {
public:int maxSubArray(vector<int>& nums) {int size = nums.size();//vector<int> dp(size);//dp[i]表示以i位置结尾的连续子数组的最大和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;}
};