题目一：
最短无序连续子数组
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
- 输入的数组长度范围在 [1, 10,000]。
- 输入的数组可能包含重复元素 ，所以升序的意思是<=。
思路：一开始就想到从两边往中间找，然而被重复数的情况弄的快自闭了，正确的姿势是，一个循环，在里面更新两边的下标
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int len = nums.size();
int r = nums[];
int l = nums[len - ];
int beg = -;
int end = -;
for (int i = ; i < len; i++) {
r = max(r, nums[i]);
l = min(l, nums[len - i - ]);
if (r > nums[i]) {
end = i;
}
if (l < nums[len - i - ]) {
beg = len - i - ;
}
}
return end - beg + ;
}
};
题目二：和为K的子数组
https://leetcode-cn.com/problems/subarray-sum-equals-k/description/
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
- 数组的长度为 [1, 20,000]。
- 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
思路：这种子数组和的问题都可以yonghash来做到复杂度o（n），hash表中存储到当前i位置的sum和，如果sum-k存在的话，那么一定有j使得arr[j+1....i]的和为k，这里看了别人的代码我发现map默认初始为0，我还在用if判断。。。
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int sum = , cnt = ;
map<int, int> hash;
hash[] = ;
for(auto n:nums) {
sum += n;
cnt += hash[sum-k];
++hash[sum];
}
return cnt;
}
};
题目三：连续的子数组和
给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1:
输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2:
输入: [23,2,6,4,7], k = 6
输出: True
解释: [23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明:
- 数组的长度不会超过10,000。
- 你可以认为所有数字总和在 32 位有符号整数范围内。
思路：和上一题一样用map记录当前到i的和的下标，就能在o（n）完成，这道题有一个点就是当k==0时，要是的第一个数是0的时候下标相减够长度小于2，所以初始化m[0]=-1
class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
map<int,int> m ;
int sum = ;
m[] = - ;
for(int i=;i<nums.size();i++){
sum+=nums[i] ;
int tmp = k==? sum : sum%k ;
if(m.count(tmp)){
if((i-m[tmp])>)
return true ;
}else{
m[tmp] = i ;
}
}
return false ;
}
};