数组要注意越界问题

一.数组的和

一般转化为有序，但是如果是返回位置而不是数的集合，就要用到hashtable

1.两数之和（数组无序，返回位置）

1.申请一个hash_table unordered_map<int, int> hash； 2.遍历数组，令num = target - nums[i]; 2.1.如果num已经在hash_map中了，那就返回hash[num]和i 2.2.否则把nums[i]-i存在hash_map

for (int i = 0; i < nums.size(); i++) { int num = target - nums[i]; if (hash.find(num)!=hash.end()) //存在 return {hash[num],i}; hash[nums[i]] = i; } return result;

167. 两数之和 II - 输入有序数组

while(i<j)//双向遍历 { if(numbers[i]+numbers[j]==target) return {i+1,j+1}; if(numbers[i]+numbers[j] < target) ++i; if(numbers[i]+numbers[j] > target) --j; }

15. 三数之和（数组无序，返回元素）

sort(nums.begin(), nums.end());//1.排序 for (int i = 0; i < n - 2; ++i)//2. 0-n-3遍历 {//先确定一个值，再双向遍历找另外两个 int l = i + 1, r = n - 1;//2.1双向遍历 //2.1.和为0一定有正有负或者3个数为0，如果三个数没有负值，那就return吧 if (nums[i] > 0) return v; //2.2.最小的sum都大于target，因此return; if (nums[i] + nums[l] + nums[l+1] > 0) break; //2.3.找到可以组成targrt的最小的num；num+sum2_max<target则continue; if (nums[i] + nums[n-1] + nums[n-2] < 0) continue; while (l < r) //3.前后双向遍历， { if (nums[i] + nums[l] + nums[r] == 0)//3.1.如果找到了另外2个值 { v.push_back({nums[i], nums[l], nums[r]});//就把其放入v //然后跳过重复值 while(nums[i] == nums[i + 1]) ++i; while(nums[l] == nums[l+1]) ++l; while(nums[r] == nums[r-1]) --r; //移动 --r;++l; } else if (nums[i] + nums[l] + nums[r] < 0) ++l;//3.2 ++l else --r; //3.3 --r } } return v;

18.四数之和（数组无序，返回元素）

sort(nums.begin(), nums.end());//1.排序 for (int i = 0; i < n - 3; i ++) //2.确定第1个值 { if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) //2.1.最小的sum都大于target，因此return return v; if (nums[i] + nums[n - 1] + nums[n - 2] + nums[n - 3] < target) //2.2找到可以组成targrt的最小的num；num+sum3_max<target则continue continue; for (int j = i + 1; j < n - 2; j ++) //3.确定第2个值 { int l = j + 1; int r = n - 1; //3.1 nums[j]的值过大,导致2.2.最小的sum都大于target，因此本次所有j遍历结束,下一个i if (nums[i] + nums[j] + nums[l] + nums[l + 1] > target) break; //3.2 本次nums[j]再加sum2_max都小于target，continue吧 if (nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target) continue; while (l < r) //4.双向遍历 { if (nums[i] + nums[j] + nums[l] + nums[r] == target) //4.1满足条件 { v.push_back({nums[i], nums[j], nums[l], nums[r]}); //4.1.1跳到最左/右边的重复值 while (nums[i] == nums[i + 1]) ++i; while (nums[j] == nums[j + 1]) ++j; while (nums[l] == nums[l + 1]) ++l; while (nums[r] == nums[r - 1]) --r; ++l; --r; } else if (nums[i] + nums[j] + nums[l] + nums[r] < target) //4.2 sum < targe，l右移 l++; else r--;//4.3 sum > targer，左移 } } } return v;

16. 最接近的三数之和

sort(nums.begin(),nums.end());//1.先排序 int min_dif=INT_MAX,dif; for(int i =0;i<n-1;++i){//2.确定第一个数 j=i+1;k=n-1; while(j<k)//3.双向遍历，重复的数也可以使用 { sum = nums[i] + nums[j] + nums[k]; dif = sum-target; if(abs(dif)<min_dif)//更新 { res=sum; min_dif=abs(dif); } //移动 if(dif<0) j++; if(dif>0) k--; if(dif==0) return res; } } return res;

二. 组合总和

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。

vector<vector<int> > combinationSum(vector<int> &candidates, int target) { sort(candidates.begin(), candidates.end());//1.排序 vector<vector<int> > v; vector<int> tmp; combinationSum(candidates, target, v, tmp, 0);//调用递归函数 return v; } void combinationSum(vector<int>& candidates, int target, vector<vector<int> >& v, vector<int>& tmp, int begin) { if (target==0) //1.只有target恰好减为0时，才加入v； { v.push_back(tmp); return; } //每一层都有一个for，以此来找最终符合target==0条件的tmp for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) //从begin开始遍历 { tmp.push_back(candidates[i]); //只要target >= candidates[i]，就往下一层递归 //target 不断减小，combination不断加入新的值，begin在++ combinationSum(candidates, target - candidates[i], v, tmp, i); tmp.pop_back();//下一层不满足target=0，上一层就pop_back， } }

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。

vector<vector<int> > combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end());//1.排序 vector<vector<int> > v; vector<int> tmp; solver(candidates, target, v, tmp, 0);//2.递归 return v; } void solver(vector<int>& candidates, int target, vector<vector<int> >& v, vector<int>& tmp, int beg) { if(target==0)//3.最终恰好减为1，tmp才符合条件 { v.push_back(tmp);//3.1加入v return; } for (int i=beg; i<candidates.size() && candidates[i]<=target; i++)//4.每一递归层，满足candidates[i]<=target，则继续for遍历 { if (i!=beg && candidates[i]==candidates[i-1]) //**4.1 保证每个数字在每个组合中只能使用一次 continue; tmp.push_back(candidates[i]);//4.2 //**4.3. 递归， target-candidates[i] ，i+1保证每个数字在每个组合中只能使用一次 solver(candidates, target-candidates[i], v, tmp , i+1); tmp.pop_back();//4.3 保证每层只push_back一个元素 } }

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有1 - 9的正整数，并且每种组合中不存在重复的数字。 注：0~9中k个数和为n,就是在 组合总和II 的基础上， 限制了0<target<50； 1<k<10； 数组中的元素为[1~9]，并且无重复； 并且限制了元素个数为k。

vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int> > v; vector<int> tmp; //1.因为是已排序，不用再排序，可以看成0~9，只不过从1开始算,则是为了保证下标和数值是一致的 help(k, n, v, tmp, 1); return v; } void help(int k, int target, vector<vector<int> >& v, vector<int>& tmp, int beg) { if (target < 0 || k > 9|| beg > 10 || tmp.size() > k ) //2.特殊条件判断 return; if (target == 0 && tmp.size() == k) //3.恰好target == 0，并且同时tmp.size() == k才放入v { v.push_back(tmp); return; } for (int i = beg; i < 10 && i<=target; i++) //4.i<=target { tmp.push_back(i); help(k, target - i, v, tmp, i + 1); //5.递归；i+1，保证不重复 tmp.pop_back(); } }

“`

216. 组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

53. 最大子序和（动态规划）

dp[i]：以i为最后一个元素，最大 连续子数组和：dp[i] = nums[i] + max(dp[i - 1] , 0 );，可以看出只要maxsum>0,他就是有价值的。 “`cpp int maxSubArray(vector& nums) { int n = nums.size(); vector dp(n,0); dp[0] = nums[0]; int maxsum = dp[0]; for(int i = 1; i < n; i++) { dp[i] = nums[i] + max(dp[i - 1] , 0 ); maxsum = max(maxsum, dp[i]); } return maxsum; }