目录
一，存在重复元素?
217. 存在重复元素 - 力扣（LeetCode）
https://leetcode.cn/problems/contains-duplicate/
?答案写在下面的函数里面：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
}
};首先，我们要达到会解的这个境界，这是最简单的境界，”暴力“
1，暴力解法：（遍历）
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
for(int i = 0; i < nums.size() -1; i++){
for(int j = 0; j < nums.size(); j++){
if(nums[i]==nums[j] && i != j ){
return ture;
}
}
}
return false;
}
};复杂度分析：
时间复杂度：O(N^2)，其中?NN?为数组的长度。需要对数组进行排序。
2，排序：
在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == nums[i + 1])
return true;
}
return false;
}
};- 这里不能写i++，也不能写++i，因为上面的循环条件里面已经有了i++，如果是写++i，i的值会重复加两遍。如果写i++的话，这里的i并没有加一，所以只会返回false。
如果一定要写++i的话也是可行的，将循环条件中的i++去掉即可。 -
时间复杂度：O(NlogN)，其中?N?为数组的长度。需要对数组进行排序。
3，哈希表：
对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> s;//建立一个哈希表
for (int x: nums) {
if (s.find(x) != s.end()) {
return true;
}
s.insert(x);
}
return false;
}
};
复杂度分析
-
时间复杂度：O(N)，其中?N?为数组的长度。
通过这个题目，我们引出了一个问题：叫做数组验重。
二，最大子数组和（最大子列和）
53. 最大子数组和 - 力扣（LeetCode）https://leetcode.cn/problems/maximum-subarray/
答案写到下面的函数里：?
class Solution {
public:
int maxSubArray(vector<int>& nums) {
}
};1，动态规划：
因此我们只需要求出每个位置的 f(i)，然后返回 f数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考虑 nums[i] 单独成为一段还是加入 f(i-1)?对应的那一段，这取决于 nums[i] 和 f(i-1) + nums[i] 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：
f(i)=max{f(i?1)+nums[i],nums[i]}
不难给出一个时间复杂度 O(n)、空间复杂度 O(n) 的实现，即用一个 f?数组来保存 f(i) 的值，用一个循环求出所有 f(i)。考虑到 f(i)只和 f(i?1) 相关，于是我们可以只用一个变量 pre 来维护对于当前 f(i)的 f(i?1) 的值是多少，从而让空间复杂度降低到 O(1)，这有点类似「滚动数组」的思想。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
};
复杂度
时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)。我们只需要常数空间存放若干变量。
2，分治：
思路和算法
这个分治方法类似于「线段树求解最长公共上升子序列问题」的 pushUp 操作。 也许读者还没有接触过线段树，没有关系，方法二的内容假设你没有任何线段树的基础。当然，如果读者有兴趣的话，推荐阅读线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」，还是非常有趣的。
我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l,r] 区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 [l,r]，我们取 m ，对区间 [l,m] 和 [m+1,r] 分治求解。当递归逐层深入直到区间长度缩小为 11 的时候，递归「开始回升」。这个时候我们考虑如何通过 [l,m] 区间的信息和 [m+1,r] 区间的信息合并成区间[l,r] 的信息。最关键的两个问题是：
我们要维护区间的哪些信息呢？
我们如何合并这些信息呢？
对于一个区间[l,r]，我们可以维护四个量：
lSum 表示 [l,r] 内以 ll 为左端点的最大子段和
rSum 表示 [l,r] 内以 rr 为右端点的最大子段和
mSum 表示[l,r] 内的最大子段和
iSum 表示 [l,r] 的区间和
以下简称 [l,m] 为 [l,r]的「左子区间」，[m+1,r] 为[l,r] 的「右子区间」。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到 [l,r][l,r] 的信息）？对于长度为 1?的区间[i,i]，四个量的值都和 nums[i] 相等。对于长度大于 1?的区间：
首先最好维护的是 \textit{iSum}iSum，区间 [l,r] 的 iSum 就等于「左子区间」的iSum 加上「右子区间」的 iSum。
对于[l,r] 的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的lSum，二者取大。
对于 [l,r] 的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
当计算好上面的三个量之后，就很好计算[l,r] 的mSum 了。我们可以考虑[l,r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l,r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。
这样问题就得到了解决。
class Solution {
public:
struct Status {
int lSum, rSum, mSum, iSum;
};
Status pushUp(Status l, Status r) {
int iSum = l.iSum + r.iSum;
int lSum = max(l.lSum, l.iSum + r.lSum);
int rSum = max(r.rSum, r.iSum + l.rSum);
int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
return (Status) {lSum, rSum, mSum, iSum};
};
Status get(vector<int> &a, int l, int r) {
if (l == r) {
return (Status) {a[l], a[l], a[l], a[l]};
}
int m = (l + r) >> 1;
Status lSub = get(a, l, m);
Status rSub = get(a, m + 1, r);
return pushUp(lSub, rSub);
}
int maxSubArray(vector<int>& nums) {
return get(nums, 0, nums.size() - 1).mSum;
}
};
复杂度分析
假设序列 a 的长度为 n。
时间复杂度：假设我们把递归的过程看作是一颗二叉树的先序遍历，那么这颗二叉树的深度的渐进上界为 O(logn)，这里的总时间相当于遍历这颗二叉树的所有节点，故总时间的渐进上界是?
故渐进时间复杂度为 O(n)。
空间复杂度：递归会使用 O(logn) 的栈空间，故渐进空间复杂度为 O(\log n)O(logn)。
「方法二」相较于「方法一」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。那么这种方法存在的意义是什么呢？
对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间 [0, n-1]，还可以用于解决任意的子区间 [l,r]的问题。如果我们把 [0,n?1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一颗真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是上文提及的一种神奇的数据结构——线段树。
https://leetcode.cn/problems/maximum-subarray/solution/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/3,暴力：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int res = nums[0];
int sum = 0;
for (int num : nums) {
if (sum > 0)
sum += num;
else
sum = num;
res = max(res, sum);
}
return res;
}
};最大子序和 - 最大子数组和 - 力扣（LeetCode）?上述解答部分来自力扣官方解答。