【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为空的情况，此时的最长连续序列就是0
return 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];
else
tmp = 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];
else
dp[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];
else
dp2 = nums[i];
max_sum = std::max(max_sum,dp2);
dp1 = dp2;//更新dp1
}
return max_sum;
}
};