一：有序数组两数之和
?
?注意：
- 这里要求两个索引是不同的，不能用一个索引取两次凑target,而且索引从1开始
- 存在解？唯一解？
法一：看见有序，想到二分查找
首先复习一下二分查找 int binarySearch(vector<int>& nums,int target){ //传入数组和查找值，返回查找结果 int L=0; int R=nums.size()-1; while(L<=R){//范围：[L,R]---左闭右闭 int mid=(L+R)/2; if(nums[mid]==target) return mid; else if(nums[mid]>target) R=mid-1; else L=mid+1; } return -1;//没找到 }本题思路：从头遍历数组，然后取后面二分查找符合题意的
class Solution { public: int binarySearch(vector<int>& nums,int target,int L){ //补充左边界 int R=nums.size()-1; while(L<=R){ int mid=(L+R)/2; if(nums[mid]==target) return mid; else if(nums[mid]>target) R=mid-1; else L=mid+1; } return -1; } vector<int> twoSum(vector<int>& numbers, int target) { int res[2]={0}; for(int i=0;i<numbers.size();i++){ //从i+1的位置，去找target-numbers[i] int p=binarySearch(numbers,target-numbers[i],i+1); if(p>0){ //都加1，索引从1开始 res[0]=i+1; res[1]=p+1; } } return vector<int>(res,res+2);//数组长是2 } };
法二：对撞指针?
首先将i,j指针指向有序数组两端，如果恰好相等，满足题意
如果和小了，应该扩大数值，很自然，只能将i右移
?
?如果和大了，应该缩小数值，相应的将j左移
?最后，一定在某个位置得到所求（题目保证必有解）
vector<int> twoSum(vector<int>& numbers, int target) { //初始化指向数组两端的指针：i和j int i=0; int j=numbers.size()-1; while(i<j){//题目不能让i,j对应一个元素 if(numbers[i]+numbers[j]==target){ int res[2]={i+1,j+1}; return vector<int>(res,res+2); } else if(numbers[i]+numbers[j]<target) i++; else j--; } //假设没有解，抛出个一场 throw invalid_argument("The input has no solution!"); }思路很清晰，如果没有边界，选择抛出异常也是个很好的选择
?二：最小子数组
?注意：连续子数组，如果不存在符合条件的子数组，返回?
0?
? ? ? ? 如图：指针i和j对应了一个区间，起始只要sum比所求小，j就不断右移，该窗口就一直扩大，直至满足了条件----和大于目标值，记录此时的窗口长度。
?
? ? ? ? 此时，i不断右移，目的是缩小窗口，在原来和的基础上求最小。如果出现sum小于目标值，i就停止，这时候j又可以右移了。如此循环
这种双索引技术叫“滑动窗口”，利用了连续的定义，窗口值一直在变，但是i,j在数组滑动的过程，逐渐找到所求 class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int minLen=nums.size()+1;//开始无解 //双索引i,j形成连续子数组和的窗口:[i,j],初始化时候没窗口 int i=0; int j=-1;//右小于左时没窗口 int sum=0; /*串口滑动*/ while(i<nums.size()){//i可以移动，j一定可以 /*每次循环移动j或i----二选一，一步步移动*/ if(j+1<nums.size()&&sum<target) //++j也要满足取值范围 sum+=nums[++j];//先移动再求和 else //sum>=target sum-=nums[i++];//先减值再移动 /*满足条件更新minLen*/ if(sum>=target) minLen=min(minLen,j-i+1);//串口大小：索引相减加一 } //无解 if(minLen==nums.size()+1) return 0; return minLen; } };仔细体会代码思想
三：无重复字符的最长子串?
?
?这个思路和滑动窗口一致：
既然只要求大小，那么用查找表存无重复的元素：
滑动过程-----
- 查找表不存在当前j指向元素，j不断右移扩大窗口；
- 如果找到了重复字符，那么j不断左移缩小窗口。
由于取最大，每次移动一次更新一次目标长度值
下面分别用map和set实现该算法 class Solution { public: int lengthOfLongestSubstring(string s) {//用set实现 /*初始化变量：i,j窗口指针、len返回值*/ int i=0; int j=-1;//[i,j]无元素 int len=0;//max set<char> record;//set查找表 while(i<s.length()){//i可继续移动 if(j+1<s.length()&&record.find(s[j+1])==record.end()){//找不到 //j可以向右移动 record.insert(s[++j]); } else{//查找表有重复元素 record.erase(s[i++]);//i右移 } //更新len len=max(len,j-i+1); } return len; } };class Solution { public: int lengthOfLongestSubstring(string s) {//用set实现 /*初始化变量：i,j窗口指针、len返回值*/ int i=0; int j=-1;//[i,j]无元素 int len=0;//max map<char,int> record;//map查找表 while(i<s.length()){//i可继续移动 if(j+1<s.length()&&record[s[j+1]]==0){//找不到 //j可以向右移动 record[s[++j]]++; } else{//查找表有重复元素 record[s[i++]]--;//i右移 } //更新len len=max(len,j-i+1); } return len; } };
