ハッシュアルゴリズム(ハッシュアルゴリズム)単純運用

1252 ワード

ハッシュアルゴリズム
今日はLeetCodeをするときに3番目の問題をやり遂げ、重複文字を含まないサブ文字列の最大長さは、ハッシュ検索の高速性を深く意識しています.
核心思想:空間で時間を変える
ハッシュアルゴリズムの核心思想は空間の複雑さで時間の複雑さを取り替えることであり、簡単に言えば、一般的な検索はデータ構造全体を遍歴することであなたの望む値を見つける必要がありますが、ハッシュアルゴリズムはまずあなたが探したいキーワードを特定の場所に保存し、キーワードを通じて直接彼を見つけることができ、データ全体を遍歴する必要はありません.ほとんどのハッシュ検索の時間的複雑さは0(n)である.
コード例
ここでは2つの簡単なコード例を直接貼ります.1つ目は最も基礎的なTwoSumです.

    vector twoSum(vector& nums, int target) {
        int n = nums.size();
        vector rev;
        map m;
        for(int i = 0;i

ここでmapコンテナを用いて簡単なハッシュテーブルを構築したことがわかる.2つ目は私の3番目の問題です.
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int rev = 0,left = 0;
        int n = s.size();
        int m[256] = {0};
        for(int i = 0; i

簡単ですが、少し理解しにくいですが、ここでは配列で簡単なハッシュテーブルを直接構築し、スライドウィンドウの検索文字列方式を形成し、正常な暴力検索では3回の時間複雑さが必要です.
c++中
c++では主にmapとsetコンテナによってハッシュテーブルの確立が可能であり,原理はkey−valueの対応である.
まとめ
ここではハッシュテーブルの簡単な使い方にすぎませんが、チェーンでハッシュテーブルを構築する方法は後で補完する機会があるでしょう.強力なデータ構造で、柔軟に運用する必要があります.