- todo
** 3】 Two Sum **
简单的开始，第一是暴力法，第二是one pass hash 如下：
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
unordered_map<int, int> mym;
for (int i=0; i<nums.size(); ++i) {
if ( mym.find(nums[i]) != mym.end() && 2*nums[i] == target )
return ret = { mym[nums[i]], i};
else
mym.insert({nums[i],i});
}
for ( int i=0; i<nums.size()-1; ++i ){
if ( mym.find(target-nums[i]) != mym.end() && mym[target-nums[i]] != i)
return ret = {i,mym[target-nums[i]]};
}
return ret;
} ```
超过45%， 还可以用one pass， 一边看已插入的有没有满足
```c++
vector<int> twoSum(vector<int>& nums, int target) {
if ( nums.empty() ) return {};
unordered_map<int, int> mym{};
for ( int i=0; i<nums.size(); ++i ) {
if ( mym.find(target-nums[i]) != mym.end() ) {
return {mym[target-nums[i]], i};
} else {
mym[nums[i]] = i;
}
}
return {};//c++11 list init
}
```
然而62%，回头看怎么快
** 1】马克马克 [Median of Two Sorted Arrays](https://leetcode.com/problems/median-of-two-sorted-arrays/)**
经典的hard，本来以为自己会了诶果然还是要动手写。各种bug
1）忽略了int/int自动的casting
2）先列出所有情况再合并
3）思路不够清楚，其实还是看了答案觉得用了s1，s2之后可读不少。还有让ar1总是最小的那个减少了subcases。关键是那句//for two arrs, cut out left parts whose total size is k, na+nb=k。
``` c++
float findKth(vector<int>& ar1, vector<int>& ar2, int k) {
int s1 = ar1.size(), s2 = ar2.size();
if (s1+s2<k || k<1 ) return -1;
//simplify by keeping smaller array come first
else if (s1>s2) return findKth(ar2, ar1, k);
else if (!s1) return ar2[k-1];
else if (k==1) return min(ar1[0], ar2[0]);
else {
//for two arrs, cut out left parts whose total size is k, na+nb=k
int na = min(k/2, s1); //why wanted to use ceil(k/2-1) before?
int nb = k-na;
if (ar1[na-1]==ar2[nb-1]) return ar1[na-1];
else if (ar1[na-1]>ar2[nb-1]) {
vector<int> newar{ar2.begin()+nb, ar2.end()};
return findKth(ar1, newar, k-nb);
} else {
vector<int> newar{ar1.begin()+na, ar1.end()};
return findKth(newar, ar2, k-na);
}
}
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int total = nums1.size()+nums2.size();
if ( total%2 == 1 ) return findKth(nums1, nums2, total/2+1);
else {
// cout<<findKth(nums1, nums2, total/2);
// cout<<" "<<findKth(nums1, nums2, total/2+1);
return ( findKth(nums1, nums2, total/2) + findKth(nums1, nums2, total/2+1) )/2;
}
}
说是hard都要半小时内bugfree呢。(⊙v⊙)嗯
