时间复杂度度量了算法在时间维度上的性能，目前也是算法最为重要的评价标准。
一、使用场景
例如下题目：
?使用通用解决思路代码如下：
/*
先计算出前缀和
1.计算出区间值
2.在根据不同尺度判断出是不是需要的数据
*/
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int findSize = 0;
//计算出前缀和
int ss = nums.size();
vector<int> sum(ss,0);
sum[0] = nums[0];
for(int i=1; i<nums.size(); i++)
{
//1个尺度的统计
if (nums[i-1] == k)
{
findSize++;
}
sum[i] = sum[i-1] + nums[i-1];
cout<<"------------ : "<<sum[i]<<endl;
}
//进行多尺度的遍历,区间尺度从2开始
for(int i=2; i <= nums.size(); i++)
{
findSize += subarraySumNode(sum, i, k);
}
return findSize;
}
//进行多尺度的遍历，比对查找
int subarraySumNode(vector<int>& nums, int scale, int k)
{
int ret = 0;
for (int i=0; i<nums.size()-scale + 1;i++)
{
if(i-1 < 0 && nums[i+scale] == k)
{
ret++;
}
else if (nums[i+scale] - nums[i-1] == k)
{
ret++;
}
}
return ret;
}
};以上代码思路比较简单，遍历数组中的所有连续子数组进行判断，但是在数据量较大时，算法较耗时。
采用下面的算法解决，耗时则 较少
/*
1. 先计算出前缀和，并将前缀和放入表中；
2. 如果前缀和等于K，则结果加一
3. 如果两个前缀和的差为K，也可以证明存在连续数组，使得连续数组的和为K
*/
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
//表示从 nums[0] 到 nums[i] 所有数的和
int sums = nums[0];
//记录sums相同和的次数
unordered_map<int,int> hash;
hash[nums[0]] = 1;
int res = 0;
if(nums[0] == k)
{
res = 1;
}
for(int i = 1; i < nums.size();++i)
{
//迭代计算sums和hash
//并根据sums和hash中结果更新计数
sums += nums[i];
if(sums == k)
{
++res;
}
if(hash.count(sums - k))
//如果在 nums[i] 前面存在和为 sums[i] - k时
//那么以该位置处到i的子数组和为 k，更新res
{ res += hash[sums - k];
}
if(hash.count(sums))
//如果hash中存在该和，则对应计数加一
{
++hash[sums];
}
else
//不存在hash中，计数为1
{
hash[sums] = 1;
}
}
return res;
}
};
