数据结构基础day5

题目：334. 递增的三元子序列

我的解法：三层循环（超时）

其他解法1：双向遍历

找第i个位置左边最小的值和右边最大的值

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n = nums.size();if(n<3) return false;	//特判vector<int> min_(n);	//左边最小的数min_[0]=nums[0];	//从最左边开始遍历for(int i=1; i<n; ++i){	//注意i=1开始min_[i] = min(min_[i-1], nums[i]);}vector<int> max_(n);	//右边最大的数max_[n-1]=nums[n-1];	//从最右边开始遍历for(int i=n-2; i>=0; --i){	//注意i=n-2max_[i] = max(max_[i+1], nums[i]);}for(int i=1; i<n-1; ++i){	//注意i从1到n-2if(min_[i-1]<nums[i] && nums[i]<max_[i+1]){return true;}}return false;}
};

其他解法2：贪心

设置first<second，first初始值为nums[0]，second为∞，指针开始遍历third：
如果third>second，则直接返回true；
如果third<second但是third>first，则让second指向third；
如果third<first，则让first指向third。

class Solution {
public:bool increasingTriplet(vector<int>& nums) {int n = nums.size();if(n<3) return false;	//特判int first = nums[0], second = INT_MAX;	//注意∞的写法for(int i=0; i<n; ++i){int num = nums[i];if(num>second){	//third>secondreturn true;}else if(num>first){	//third<second但是third>firstsecond = num;}else{	//third<firstfirst = num;}}return false;}
};

题目：238. 除自身以外数组的乘积

我的解法：设置左右乘积数组

时间复杂度和空间复杂度都是O(n)

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> left_mul(n);left_mul[0] = 1;	//设置第i个位置左边所有数的乘积for(int i=1; i<n; ++i){left_mul[i] = left_mul[i-1] * nums[i-1];}vector<int> right_mul(n);right_mul[n-1] = 1;	//设置第i个位置右边所有数的乘积for(int i=n-2; i>=0; --i){right_mul[i] = right_mul[i+1] * nums[i+1];}vector<int> answer(n);for(int i=0; i<n; ++i){	//第i个位置的answer等于左边所有数的乘积*右边所有数的乘积answer[i] = left_mul[i] * right_mul[i];}return answer;}
};

其他解法：使用answer来充当left_mul，用实数R作为right_mul

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> answer(n);answer[0] = 1;for(int i=1; i<n; ++i){	//answer首先作为left_mulanswer[i] = answer[i-1] * nums[i-1];}int R = 1;for(int i=n-1; i>=0; --i){	//使用实数R遍历右侧乘积，乘到answer上answer[i] = answer[i] * R;R = R*nums[i];}return answer;}
};

题目：560. 和为K的子数组

我认为这道题，很重要的一点是得理解题意要求找到从i到j的一个子数组和为k，从i到j很灵性。

解法1：暴力法（超时）

时间复杂度O(n^3)

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size(), count=0;for(int i=0; i<n; ++i){	//遍历ifor(int j=i; j<n; ++j){	//遍历jint sum=0;for(int u=i; u<=j; ++u){	//i到j求和sum += nums[u];}if(sum==k) ++count;	//求和结束判断是否为k}}return count;}
};

解法2：在1上去除重复运算（超时）

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size(), count=0;for(int i=0; i<n; ++i){int sum=0;for(int j=i; j<n; ++j){	//i到j == i到j-1 + jsum += nums[j];if(sum==k) ++count;}}return count;}
};

解法3：前缀和

前缀和：从第0项到第x项的和
定义为PreSum数组，PreSum[x]表示从第0项到第x项的和
$$PreSum[x]=nums[0]+nums[1]+......+nums[x]$$
于是就有：
$$PreSum[x]=PreSum[x-1]+nums[x]$$
$$nums[x]=PreSum[x]-PreSum[x-1]$$
因此i到j的和为：
$$nums[i]+......+nums[j]=PreSum[j]-PreSum[i-1]=k$$
当i=0时，i-1=-1，因此特殊定义PreSum[-1]=0
因此题目从i到j项的子数组和为k 转换为 PreSum[j]-PreSum[i-1]=k
在本题中我们不关心具体是哪两项的PreSum之差=k，关心差出现的次数，因此引入一个hashmap来记录
遍历nums之前，放入PreSum[-1]=0，即{0,1}，表示和为0出现了1次
遍历nums时，求每一项前缀和，统计出现次数，同时关注hashmap中键为当前前缀和-k的元素（我的理解是PreSum[i-1]=PreSum[j]-k) , 将PreSum[i-1]的值累加。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size(), count=0;unordered_map<int, int> hash;	//存储前缀和和对应出现频次hash[0]=1;	//初始值为PreSum[-1]=0，因此hash的初始值为前缀和为0，出现次数为1int pre=0;	//前缀和初始值for(int i=0; i<n; ++i){pre += nums[i];	//递增计算pre前缀和if(hash.find(pre-k)!=hash.end()){	//如果能找到之前的前缀和=当前前缀和-k，则将之前的前缀和出现频次累加到count上count += hash[pre-k];}++hash[pre];	//统计该前缀和对应频次}return count;}
};