哈希表

哈希表是一种将键值联系起来的表，其特点是，比起其他的表来说，他的查询具有很高的效率，因此哈希表也经常被用于查询某些键值中。

1、两数之和

简单分析，从这里就能看出，可以通过暴力枚举所有的可能，和目标值进行匹配，但是唯一的缺点就是它的时间复杂度为O(n)，效率不高，非常的耗时间。

题解一

暴力枚举

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> a;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]+nums[j]==target){
                    a.push_back(i);
                    a.push_back(j);
                    break;
                }
            }
        }
        return a;
    }
};

题解二

哈希表进行取值，这是一种比较巧妙的方式，简单分析。

• 如果将数组的下标作为key值的话，那哈希表的就退化成了一个数值，这并不符合哈希表的特性。
• 如果将两个数的下标之和作为hash值的话，那也会造成重复的概率，这样的hash表就不是我们想要的，而且如果hash表中是以链表的形式存储的话，哈希表就有可能会退化成链表。
• 如果以两个数之和也就是target，作为hash值的话，依照题目的条件，那相同的可能性就很低了，而且我们可以刚好高效的匹配到我们想要的key值，但是，问题在于，我们通过hash值找到的value只能是一个，并且因此，这样的方式是错误的

以上是我的推导，根据这三种可能性，我想不到有任何能够做出一张令人满意的hash表，但是，我看完题解后，可能有时候，答案的来源，需要一些灵性罢了。
这是将一个数的值和另一个数的数值下标进行结合，这种结合方式巧妙的利用target作为两个数之间的中间桥梁，
另一个数，等于target减去这个数，并且把另一个数（target-num）作为key值，value为数组下标。
当我们获取到另外一个数是，刚好可以通过这个数，访问到原来减去的那个数的数组下表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int,int> table;
        vector<int> res(2);
        for(int i=0;i<nums.size();i++){
            if(table.count(nums[i])){
                res[1]=i;
                res[0]=table[nums[i]];
                return res;
            }
            table[target-nums[i]]=i;
        }
        return res;
    }
};

3、无重复的字符的最长子串

由于是字符，很容易就想到字典树或者是哈希表来处理这类问题，由于我用的是java中的hashmap去处理这个问题，设置一个index=0，遍历这个字符串，将每个字符加入的哈希表中，记录个数，当哈希表中存在字符是，记录最大个数，将哈希表删除，index++，从不同起始位置去查看字符，这样的遍历方式是O(n)，及其耗费时间。

题解一 哈希表

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int count=0;
        int max=0;
        int index=0;
        Map<Character, Integer> map=new HashMap<>();
        for(int i=index;i<s.length();i++){
            if(map.get(s.charAt(i))!=null){
                if(count>max)
                    max=count;
                    count=0;
                map.clear();
                i=++index;
            }
            map.put(s.charAt(i),1);
            count++;
        }
        if(count>max)
            max=count;
        return max;
    }
}