【HOT100第三天】和为K的子数组,最大子数组和,合并区间,轮转数组

今天练的是子串和子数组专题 ~ （前缀和那里差点学死了）

560.和为K的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

 先写个暴力法，用昨天刚学的滑动窗口👇（如果没有把nums.size()用n表示，就会接下来算两遍，然后在提交的时候超时）

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int right=1,ans=0,n=nums.size();for(int left=0;left<n;left++){int sum=0;right=left;while(right<n){sum+=nums[right++];if(sum==k){ans++;}}}return ans;}
};

因为被全世界太多人打败，去看了题解，学会了前缀和方法。发现这种方法可以处理不少数字之和问题。

我们之前在队列中学过Sn和an的关系：

 

而很好理解，我们要求就是一个这样的值 ：

 

 也可以根据上面的公式表示成这样：

简化成方便表示的形式：

 

因此，我们只需要建立一个哈希表，用来装前缀和。因为假设了 i > j ，所以我们在遍历 i 的时候， j 肯定已经被存入哈希表了，所以我们可以通过下面的公式来找出是否和为 k 的子数组是否存在：

转化成计算机语言就是 mp.contains(pre-k) 【pre表示的是当前的前缀和 Si 】。

然后通过遍历数组，不断寻找满足条件的数就好了。

值得注意的是 mp[0]=1 这部分，为什么要加上呢？？是因为对于  来讲，我们必须要考虑 Si = k 的情况，也就是 k 的值正好与某个前缀和相等的情况，而依据我们之前往哈希表中装入的数来看，我们显然是没有考虑的。所以应该提前加入mp[0]=1。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n=nums.size(), ans=0,pre=0;unordered_map<int,int> mp;mp[0]=1;for(int i=0;i<n;i++){pre+=nums[i];if(mp.contains(pre-k)) ans+=mp[pre-k];mp[pre]++;}return ans;}
};

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

刚开始想了一下是不是可以用滑动窗口，但是无序数组那样做的话时间复杂度应该会很高。所以先在草稿纸上思考一下。

假设一个数组为{-2，1，-3，4，-1，2，1，-5，4}.并且假设当前遍历的数为nums[i]，前缀和（前面所有数之和）为sum。我们可以考虑一下怎样让子数组和最大。

1.sum>=0

        (1)nums[i]>=0 执行：sum+=nums[i]

        (2)nums[i]<0 执行：sum+=nums[i]

2.sum<0

        (1)nums[i]>=0 执行：sum=nums[i]

        (2)nums[i]<0

                a. sum>=nums[i] 执行：sum+=nums[i]

                b. sum<nums[i] 执行：sum=nums[i]

不过！不要忘了考虑可能会有一种特殊情况，{-1}.如果我们一开始让sum=0，可能就会在判断里出错【因为初值比nums[0]大】，所以sum应该提前赋初值nums[0]，然后我们从i=1开始遍历。

（判断过程写if-else就好，只是三元运算符比较帅👉👈）

class Solution {
public:int maxSubArray(vector<int>& nums) {int ans = nums[0], sum = nums[0];for (int i = 1; i < nums.size(); i++) {sum = (sum >= 0 || (sum < 0 && nums[i] < 0 && sum >= nums[i])) ? (nums[i] + sum) : nums[i];ans = max(sum, ans);}return ans;}
};

 56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

以 intervals = [[1,3],[2,6],[8,10],[15,18]] 为例画一个图，就可以很快发现，要判断集合是否重合，只需要判断某一个集合的start[i]是不是在另一个集合的start[j]和end[j]中。

排序一下就更简单了，只需要和前一个数做比较即可。

我们建一个二维数组merged，放进索引为0的集合，然后从索引为1的集合开始遍历intervals，这样可以方便比较，如果重合，就改一下merged中最后一项的end值，如果没有重合就把新集合push_back进去就可以了！

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.empty()) return {};vector<vector<int>> merged;sort(intervals.begin(), intervals.end());merged.push_back(intervals[0]);for (int i = 1; i < intervals.size(); i++) {if (merged.back()[1] >= intervals[i][0]) {merged.back()[1] = max(merged.back()[1], intervals[i][1]);} else {merged.push_back(intervals[i]);}}return merged;}
};

189. 轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 :

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]

向右轮转 3 步: [5,6,7,1,2,3,4]

 最开始想着用队列实现轮转，写着写着转念一想，直接预测一下最终每一个数字的位置，然后放进一个临时数组里不就行了吗。然后就完成了下面的部分👇【注意：要提前给res数组分配空间，因为我们不是从数组的第一位开始赋值的】

class Solution {
public:void rotate(vector<int>& nums, int k) {int n=nums.size();vector<int> res(n);k=k%n;for(int i=0;i<n;i++){res[(i+k)%n]=nums[i];}nums=res;}
};

 之后发现空间复杂度有点高，可以牺牲一点时间复杂度，用小一点的数组来解决问题。

步骤：

1.把要换到数组最前面的数字放进数组 h 里

2.把nums数组往后移动k位

3.把 h 数组里的数字填入nums中

class Solution {
public:void rotate(vector<int>& nums, int k) {int n=nums.size();k=k%n;vector<int> h(k);for(int i=0;i<k;i++){h[i]=nums[n-k+i];}for(int i=0;i<n-k;i++){nums[n-i-1]=nums[n-k-i-1];}for(int i=0;i<k;i++){nums[i]=h[i];}}
};