day 2 medianOfTwoSorted & lo

• 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⊙)嗯