C++ Only ONE Hash Table with O(m+n) time


  • 0
    G
    class Solution {
    public:
        vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
            unordered_map<string, unsigned int> map2;
            for (auto i = 0; i < list2.size(); i++) {
                map2[list2[i]] = i;
            }
            
            auto min = UINT_MAX;
            vector<string> ret;
            
            for (auto i = 0 ; i < list1.size() ; i++) {
                if (map2.count(list1[i]) > 0) {
                    auto sum = i + map2[list1[i]]; // index sum
                    if (sum < min) {
                        min = sum;  // update min
                        ret.clear();
                        ret.push_back(list1[i]);
                    }else if(sum == min){
                        ret.push_back(list1[i]);
                    }
                }
            }
            
            return ret;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.