刷爆Leetcode Day2
6. 和为s的两个数字
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
//排序+双指针
sort(price.begin(),price.end());
int left=0,right=price.size()-1;
while(left<right)
{
int ret=price[left]+price[right];
if(ret>target)
{
right--;
}
else if(ret<target)
{
left++;
}
else
{
//隐式类型转换
return {price[left],price[right]};
}
}
return {};
}
};
7.三数之和
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
//延续上一题的做法，不过只是target会改变
//复杂的是这里需要去重也就是三元组之间没有交集（参考集合）
sort(nums.begin(),nums.end());
vector<vector<int>> vv;
int n=nums.size();
//i++不能在这里，否则会跳过部分元素
//三元组，因此i最多等于n-3
for(int i=0;i<n-2;)
{
//对于一个已经排好序的数组来说，正整数不需要固定了，因为三数之和一定大于0
if(nums[i]>0)
break;
int left=i+1,right=n-1,target=-nums[i];
while(left<right)
{
int sum = nums[left] + nums[right];
if(sum>target)
right--;
else if(sum<target)
left++;
else
{
vv.push_back({nums[left],nums[right],nums[i]});
left++;
right--;
//去重,防止越界如[0,0,0,0,0,0]left会减到-1
while(left<right&&nums[left]==nums[left-1])left++;
while(left<right&&nums[right]==nums[right+1])right--;
}
}
i++;
while(i<n-2&&nums[i]==nums[i-1])i++;
}
return vv;
}
};
8. 四数之和
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
//延续上一题，不过在此之上要多固定一个
sort(nums.begin(),nums.end());
vector<vector<int>> vv;
int n=nums.size();
for(int i=0;i<n-3;)
{
for(int j=i+1;j<n-2;)
{
int left=j+1,right=n-1;
while(left<right)
{
//数据太大了整形存不下来，[1000000000,1000000000,1000000000,1000000000]，用long long
//可以先去减target，nums[i]-(long long)这样的话会进行提升做64位的计算，放到后面也会存储不下来
long long aim=nums[i]-(long long)target+nums[j]+nums[right]+nums[left];
if(aim<0)
left++;
else if(aim>0)
right--;
else
{
vv.push_back({nums[left],nums[right],nums[i],nums[j]});
left++;
right--;
//去重
while(left<right&&nums[left]==nums[left-1])left++;
while(left<right&&nums[right]==nums[right+1])right--;
}
}
j++;
while(j<n-2&&nums[j]==nums[j-1])j++;
}
i++;
while(i<n-3&&nums[i]==nums[i-1])i++;
}
return vv;
}
};
9. 长度最小的子数组
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
//滑动窗口问题
//暴力求解:枚举+我们可以通过左下标和右下标划分子数组+遍历子数组求和，O（n^3）
//滑动窗口是基于“同向双指针”的思想，也就是左右指针朝一个方向移动这是基于求和的单调性
int left=0,right=-1,n=nums.size(),sum=0,len=100001;
for(int left = 0, right = 0; right < n; right++)
{
//循环进或者循环出，不要用if来判断
sum += nums[right]; // 进窗⼝
while(sum >= target) // 判断
{
len = len>right-left+1?right-left+1:len;// 更新结果
sum -= nums[left++]; // 出窗⼝
}
}
//注意len最大为100000，可能整个数组求和都小于target，此时判断len是否等于100001来判断村子不符合条件的子数组
return len == 100001 ? 0 : len;
}
};
10. 无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
//滑动窗口问题
//我们需要一个哈希表来映射相同元素以便可以去重
//对于一个重复子串，我们很容易想到除非我们跳过重复元素，否则重复子串的子串一定是减少的
//通过整形数组实现哈希表
int n=s.size();
int len=0;
// 创建⼀个哈希表，统计频次
int hash[96] = { 0 };
for (int left=0,right = 0; right < n; right++)
{
//映射
char gap=31;
// 寻找结束为⽌
hash[s[right]-31]++; // 统计字符出现的频次
while (hash[s[right]-31] > 1) // 如果出现重复的
{
hash[s[left]-31]--;
left++;
}
// 如果没有重复，就更新 ret
len=len>right-left+1?len:right-left+1;
}
return len;
}
};
原文地址：https://blog.csdn.net/Yusei_0523/article/details/142994611
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！