Day10——LeetCode15560

1 LeetCode15.三数之和(LeetCode15)

1.1 题目描述

题目描述如下：

首先大致分析一下，我们可以枚举每一个数，然后去搜索另外两个符合条件数，这不难发现，若对原数组进行排序会方便我们的搜索。

1.2 题目解决

设三元组为[a,b,c]，我们的思路是让a跑遍数组每一个数，然后去寻找符合条件的b,c。
首先对原数组进行排序，因为我们让a跑遍数组的所有元素，因此b,c只需要跑遍a的右部分即可，这样简化了穷搜的思路。然后观察，由于我们已经对数组进行了升序排序，因此我们可以从a的右部分的两头开始搜索(b初始在a后一个，c初始在数组最后)：若a+b+c<0，说明我们需要更大的b+c，因此我们需要向右移动b使b减小；反之向左移动c使c减小，直到找到a+b+c=0，将其写入答案中。
这里我们要注意，上述过程会产生重复答案。分析重复的情况，第一种重复，若对于a=a1我们已经搜索过相应的b,c了，因为我们已经对数组排好序，所以若下一个a也为a1，则我们不需要再搜索。另一种重复，在a=a1的搜索过程中，若找到了b=b1，c=c1这一组解，我们需要继续向右移动b，向左移动c看是否还有另一组解，若下一个b仍为b1，则我们也不需要进行搜索了，直接跳过进行下一个b，因为已经对a,b产生的重复进行了处理，所以跳过这些可能引起重复的a,b后，c即使重复也不会被重复写入答案中。
具体代码及注释如下：

#include<algorithm>
#include<vector>
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;int n=nums.size();sort(nums.begin(),nums.end());//固定第一个数为nums[0],...,nums[n-1];for(int i=0;i<n;i++){//如果第一个数与前一个数相等，说明前一个数已经找过了，跳过此次循环if(i>0&&nums[i]==nums[i-1]) continue;//寻找第二个数和第三个数的位置left和rightint right=n-1,left=i+1;while(left<right){int sum=nums[i]+nums[left]+nums[right];//第二个数前面也寻找过了，则跳过，继续从下一个位置寻找第二个数if(left>i+1&&nums[left]==nums[left-1]){left++;continue;}/*上面换成这样也对if(right<n-1&&nums[right]==nums[right+1]){right--;continue;}*///三数之和大于0.说明第二个数和第三个数之和太大，于是减小第三个数，right--if(sum>0){right--;}//与上相反，left++if(sum<0){left++;}//等于0则加入结果，继续寻找看是否还有以nums[i]为第一个数的解if(sum==0){ans.push_back({nums[i],nums[left],nums[right]});left++;right--;}}}return ans;}
};

1.3 复杂度分析

算法有两层循环，时间复杂度为 $O(n^2)$ ，若不算结果数组，则空间复杂度为 $O (1)$ 。

2 LeetCode560.和为k的子数组(LeetCode560)

2.1 题目描述

题目描述如下：

几个示例：

2.2 问题解决

设sum[i]= $\sum_{k=0}^{i}\text{nums[i]}$ ，如果你发现i>j,sum[i]-sum[j]=nums[i+1]+nums[i+2]+...+nums[j]，则就找到了该题的关键。
我们只需要将前i个元素的和插入到哈希表中，然后在遍历数组的过程中记录下当前元素及其之前的元素的和sum[i]，查找哈希表sum[i]-k出现的次数，即是和为k的子数组的个数。
代码如下：

#include<iostream>
#include<unordered_map>
using namespace std;
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> hash;hash[0]=1;int n=nums.size();int pre_sum=0;int ans=0;for(int i=0;i<n;i++){//记录前缀和pre_sum+=nums[i];//查找是否能与前面的某个元素构成和为k的子数组if(hash.find(pre_sum-k)!=hash.end()){ans+=hash[pre_sum-k];}hash[pre_sum]++;}return ans;}
};