哈希表

哈希表(hashmap)做为一种数据结构，在解决算法问题时起到了非常多的作用，以下这些例题便是用到了hashmap来对题目进行巧妙的解答。

525. 连续数组

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

输入: [0,1]

输出: 2

说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: [0,1,0]

输出: 2

说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

注意: 给定的二进制数组的长度不会超过50000。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/contiguous-array

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题的关键思路点在与对于0和1的处理，如果去计算总和的时候，当遇到0的时候-1，当遇到1的时候+1. 然后我们把计算的和称为count，并用hashmap去进行存储，hashmap的第一个值存储的是count，第二个值存储的是该count所首次对应的index值。在从左往右去遍历链表的时候，如果发现当前index所得出的count值在hashmap中出现过，则计算该index到存储在count中的index的值的距离。

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        map<int, int>conmap;
        conmap[0] = -1;
        int maxlen = 0;
        int count = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            count += nums[i] == 1? 1 : -1;
            if(conmap.find(count) != conmap.end())
                maxlen = max(maxlen, i - conmap[count]);
            else
                conmap[count] = i;
        }
        return maxlen;
    }
};