主要应用的是Hash Table

• 要对每种基础数据结构有深刻的理解。主要应对设计题：
• HashTable： 增、删、查都是O(1)，但是是无序的
• vector: 增(尾部增O(1)、其他O(n))、删(尾部删O(1)、其他O(n))、查(O(n)),可以有序可以无序
• list: 增、删(头尾O(1)、其他O(n))、查(O(n))

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

使用Hash Table保存遍历过的元素，从而达到降低时间复杂度到O(n)。利用到的技巧：1. 边遍历边加入Hash Table中。 2. 在Hash Table中找差值

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> res;
    unordered_map<int, int> dict;
    for (int i = 0; i < nums.size(); ++i) {
        int toGet = target - nums[i];
        if (dict.find(toGet) != dict.end()) {
            res.push_back(dict[toGet]);
            res.push_back(i);
            return res;
        }
        dict[nums[i]] = i;
    }
    return res;
}

36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.

数独是否可解，数独的三个条件 1. 行不重复 2. 列不重复 3. 3*3子矩阵不重复。使用数组做词典来比较。

bool isValidSudoku(vector<vector<char>>& board) {
    int row[9][9] = {0}, column[9][9] = {0}, subBox[9][9] = {0};
    
    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[0].size(); ++j) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '0' - 1;
                int sub = i/3*3 + j/3;
                if (row[i][num] || column[j][num] || subBox[sub][num]) return false;
                row[i][num] = column[j][num] = subBox[sub][num] = 1;
            }
        }
    }
    
    return true;
}

146. LRU Cache

实现LRU，即优先抛弃最近未命中

使用list保存key值，unordered_map保存key value对应的对，unordered_map保存key 位置对应的对。

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        if (key2value.find(key) != key2value.end()) {
            keys.erase(key2loc[key]);
            keys.push_front(key);
            key2loc[key] = keys.begin();
            
            return key2value[key];
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {
        if (key2value.find(key) != key2value.end()) {
                key2value[key] = value;
                
                keys.erase(key2loc[key]);
                keys.push_front(key);
                key2loc[key] = keys.begin();
        } else { 
            if (keys.size() == cap) {
                    key2value.erase(key2value.find(keys.back()));
                    key2loc.erase(key2loc.find(keys.back()));
                    keys.pop_back();
                    
                    keys.push_front(key);
                    key2value[key] = value;
                    key2loc[key] = keys.begin();
            } else {
                keys.push_front(key);
                key2value[key] = value;
                key2loc[key] = keys.begin();
            }
        }
   }
private:
    unordered_map<int, int> key2value;
    unordered_map<int, list<int>::iterator> key2loc; 
    list<int> keys;
    int cap;
};

30. Substring with Concatenation of All Words

所有字符串拼接出来的起始位置。 注意：有可能字符串有可能重复，所以使用map保存其出现次数。for循环的步长为1， 结束条件为剩余长度为n-1。

vector<int> findSubstring(string s, vector<string>& words) {
    int m = words.size(), n = m?words[0].size():0;
    vector<int> res;
    if (!m || !n || s.size() < m*n) return res;
    
    unordered_map<string, int> words_count;
    for (auto word:words) words_count[word]++;
    
    for (int i = 0; i <= s.size() - n; ++i) {
        bool flag = true;
        unordered_map<string, int> tmp = words_count;
        for (int j = 0; j < m; ++j) {
            if (tmp[s.substr(i + j*n, n)]-- == 0) {
                flag = false;
                break;
            }
        }
        
        for (auto it = tmp.begin(); it != tmp.end(); ++it) {
            if (it -> second != 0) {
                flag = false;
                break;
            }
        }
        
        if (flag) {
            res.push_back(i);
        } 
    }
    
    return res;
}

128. Longest Consecutive Sequence

最大连续序列。使用Hash table记录数组中数值，遍历数组如果数值是新的开始，则遍历该数值能到达的长序列。得到的最大值就是结果。

int longestConsecutive(vector<int>& nums) {
    set<int> nums_set;
    for (int i = 0; i < nums.size(); ++i) {
        nums_set.insert(nums[i]);
    }
    
    int longest = 0;
    for (set<int>::iterator it = nums_set.begin(); it != nums_set.end(); ++it) {
        if (nums_set.find(*it-1) == nums_set.end()) {
            int cur = *it;
            while (nums_set.find(cur + 1) != nums_set.end()) {
                cur++;
            }
            
            longest = max(longest, cur - *it + 1);
        }
    }
    return longest;
}