刷爆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-3for(int i=0;i<n-2;){//对于一个已经排好序的数组来说，正整数不需要固定了，因为三数之和一定大于0if(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会减到-1while(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;}
};