Hash

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

unordered_map中不存在的值会被表示为 0 ， 下面这段代码输出为 2 3
0 0

1
2
3
4
5
6
7
unordered_map<int, int> hashmap;
hashmap.insert(make_pair(3, 2));
hashmap[1] = 3;
cout << hashmap[3] <<" "<< hashmap[1] << endl;
hashmap.erase(1);
cout << hashmap[1] << " "<<hashmap[-1] endl;
return 0;

LeetCode 1.Two Sum

方法一

c.count(k) 返回关键字等于k的元素的数量，对于不允许重复关键字的容器，返回值永远是 0 或 1

1
2
3
4
5
6
7
8
9
10
11
12
Class Solution {
public:
    vector<int> towSum(vector<int>& nums, int target) {
        unordered_map<int, int> mapNums;
        for (int i = 0; i < nums.size(); i++) {
            if (mapNums.count([target - nums[i]]))
                return {mapNums[target - nums[i]], i};
            mapNums[nums[i]] = i;
        }
        return {};
    }
}

方法二

c.find(k) 返回一个迭代器，指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器

1
2
3
4
5
6
7
8
9
10
11
12
Class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> mapNums;
        for (int i = 0; i < nums.size(); i++) {
            if (mapNums.find(target - nums[i]) != mapNums.end()) 
                return {mapNums[target - nums[i]], i};
            mapNums[nums[i]] = i;
        }
        return {};
    }
}

LeetCode 560. Subarray Sum Equals K

计算出从第一个数到每一个数的和，那么任意一段连续数字的和就可以通过两段和相减得出。
用sum表示从数组起始位置到当前位置所有数字的加和，用Hash Table来存储sum出现的次数，如果当前位置之前有和（prefix sum）为sum - k的位置，则这两个位置之间的数字之和为k。那么，以当前位置结尾，和为k的子数组个数为hash[sum - k]。遍历整个数组即可得出满足条件的子数组个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
 public:
  int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> hashNums;
    int sum;
    int result;
    hashNums[0] = 1;
    for(auto& num : nums) {
        sum += num;
        if (hashNums.count(sum - k))   //这个if()可以提高近一半的效率
            result += hashNums[sum - k];
        hashNums[sum]++;
    }  
    
  }
};

如下图所示，if(hashNums.count(sum - k)) 对效率的提升是很惊人的

LeetCode 49.Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mapStr;
        vector<vector<string>> result;
        
        for (string str : strs) {
            string temp = str;
            sort(temp.begin(), temp.end());
            mapStr[temp].push_back(str);
        }
        
        for (auto str : mapStr) {
            result.push_back(str.second);
        }
        
        return result;
    }
};

第一个for循环处

能自己写出类型来就不要用auto了

unordered_map 第二个类型为vector容器时的情况

使用stl的 sort函数

头文件

语法描述 sort(begin, end, cmp) cmp参数可以没有， 默认为非降序排序。
cmp:

  • 升序： less<data-type>
  • 降序： greater<data-type>
    1
    2
    int a[5] = {1, 3, 4, 2, 5};
    sort(a, a + 5, greater<int>);

LeetCode 3.Longest Substring Without Repeating Characters

使用vector记录string中的字符是否重复

当 dict[s[i]] > start时，说明在dict中 s[i]这个字符对应的索引已经被改变过， 即出现了重复的字符， 此时我们让start指向第一个重复的字符处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> dict(256, -1);
        int start = -1;
        int maxlen = 0;

        for (int i = 0; i < s.size(); i++) {
            if (dict[s[i]] > start ) {
                start = dict[s[i]];
            }
            dict[s[i]] = i;
            maxlen = max (i - start, maxlen);
        }
        return maxlen;
    }
};

使用unordered_map 代替上面的 定长数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        
        unordered_map<char, int> charMap;
        int start = -1;
        int maxLen = 0;
        
        for (int i = 0; i < s.size(); i++) {
            if (charMap.count(s[i]) != 0) {
                start = max(start, charMap[s[i]]);
            }
            charMap[s[i]] = i;
            maxLen = max(maxLen, i-start);
        }
        
        return maxLen;
    }
};

LeetCode 205. Isomorphic Strings

同构字符串。我们用两个哈希表分别来记录两个字符串中字符出现的情况，由于ASCII只有256个字符，所以我们用一个大小为256的数组来代替哈希表，并初始化为0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int a[256] = {0};
        int b[256] = {0};
        for (int i = 0; i < s.size(); i++) {
            if (a[s[i]] != b[t[i]]) {
                return false;
            }
            a[s[i]] = i + 1;
            b[t[i]] = i + 1;
        }
        return true;
    }
};

把上面的数组换成stl中的哈希表也是一样的（unordered_map<char, int>）。
这段代码的精髓在于 a[s[i]] = i + 1; 和 b[t[i]] = i + 1; ， 这里i + 1 相当于让不同位置的字符有不同的索引，避免了将aba, baa这样的string误判为同构。

LeetCode Minimum Index Sum of Two Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {
        vector<string> result;
        unordered_map<string, int> hashmap;
        int min = INT_MAX;
        
        for (int i = 0; i < list1.size(); i++) {
            hashmap[list1[i]] = i;
        }
        for (int i = 0; i < list2.size(); i++) {
            if (hashmap.count(list2[i]) > 0) {
                if (min > i + hashmap[list2[i]]) {
                    min = i + hashmap[list2[i]];
                    result.clear();
                    result.push_back(list2[i]);
                } else if (min == i + hashmap[list2[i]]) {
                    result.push_back(list2[i]);
                }
            }
        }
        return result;
    }
};

clear() 清空所有元素

C/C++ 整型的上下限 INT_MAX INT_MIN

int 占 4字节 32位， 因此：
INT_MAX = 231 - 1
INT_MIN = -231

Leetcode 349.Intersection of Two Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> hashmap;
        vector<int> result;
        for (int num1 : nums1) {
            hashmap[num1]++;
        }
        for (int num2 : nums2) {
            if (hashmap[num2] > 0) {
                result.push_back(num2);
                hashmap[num2]--;
            }
        }
        return result;
    }
};

第二个for循环处 if(hashmap[num2] > 0) 不可以替换成 hashmap.count(num2)。 因为count(key)函数是用以统计key在unordered_map中出现的次数，而unordered_map不允许存在重复的key，因此，如果key存在，则count(key) 返回 1， 否则 返回 0。 这里我犯的错误属于 对count(key) 功能的 认知错误。

LeetCode 219.Contains Duplicate II

此题错在读题不仔细， 没有意识到at most

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hashmap;
        for (int i = 0; i < nums.size(); i++) {
            if (hashmap.count(nums[i]) ) {
                if ((i - hashmap[nums[i]]) <= k) {
                    return true;
                }
            }
            hashmap[nums[i]] = i;
        }
        return false;
    }
};
0%