2017-3-12 leetcode 167 209 216

---恢复内容开始---

对于每次开机avast喊出的“已经检测到危害”实在忍无可忍了（它只能检测到不能根除很气。。）于是重装了系统，回到了win10感觉不赖。

================================================================================

leetcode167 Two Sum II

leetcode209 Minimum Size Subarray Sum

leetcode216 Combination Sum III

================================================================================

169讲的是
给你n个数字（非降序，可能重复），和一个数字target，在这n个数字中一定存在且只存在一组数字，相加等于target，输出他们的下标+1

我的思路
这道题是leetcode1的升级版，但是感觉难度是下降了啊。。。。和1的解法类似，只是不需要排序了，直接看代码吧。。

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& numbers, int target) {
 4         int n=numbers.size();
 5         vector<int> &mynum=numbers;
 6         int myend=n-1,mybegin=0;
 7         vector<int> aim;
 8         while(1){
 9             while(mynum[mybegin]+mynum[myend]>target)
10                 myend--;
11             while(mynum[mybegin]+mynum[myend]<target)
12                 mybegin++;
13             if(mynum[mybegin]+mynum[myend]==target){
14                 aim.push_back(mybegin+1);
15                 aim.push_back(myend+1);
16                 break;
17             }
18         }
19         return aim;
20     }
21 };

169

==================================================================================

209讲的是
给你n个正整数，和一个数字s，问你数组中满足条件的最短连续子序列的长度是多少？条件是子序列累加和大于等于s。

我的思路
两个指针扫，前面的负责加，后面的负责减，判断。O（n）的。

 1 class Solution {
 2 public:
 3     int minSubArrayLen(int s, vector<int>& nums) {
 4         int n=nums.size(),aim=n,eptr,sum=0,sptr=-1;
 5         if(n==0)return 0;
 6         for(eptr=0;eptr<n&&sum<s;eptr++){
 7             sum+=nums[eptr];
 8         }
 9         while(sum-nums[sptr+1]>=s){
10             sum-=nums[++sptr];
11         }
12         aim=sum>=s?(eptr-1)-sptr:0;
13         for(;eptr<n;eptr++){
14             sum+=nums[eptr];
15             while(sum-nums[sptr+1]>=s){
16                 sum-=nums[++sptr];
17             }
18             aim=min(aim,eptr-sptr);
19         }
20         return aim;
21     }
22 };

209

===================================================================================

216讲的是
给你两个数字n，k表示你需要用n个不同数字的和使其等于k，数字只能选1--9，输出所有的情况。

我的思路
深搜，枚举所有情况就行了。。。

 1 class Solution {
 2 public:
 3     vector<int> aim;
 4     vector<vector<int> > ans;
 5     void dfs(int s,int f,int sum,int n,int target){
 6         if(sum>target)return;
 7         if(f==n+1&&sum==target){
 8             this->ans.push_back(aim);
 9             return;
10         }
11         if(f==n+1)return;
12         for(int i=s;i<10;i++){
13             this->aim.push_back(i);
14             dfs(i+1,f+1,sum+i,n,target);
15             this->aim.pop_back();
16         }
17     }
18     vector<vector<int>> combinationSum3(int k, int n) {
19         dfs(1,1,0,k,n);
20         return this->ans;
21     }
22 };

216