經典Leetcode算法題分享(哈希表)

文章已收錄Github精選，歡迎Star： https://github.com/yehongzhi/learningSummary

前言

本篇文章主要講解leetcode上，關于哈希表(簡單難度)的算法題目。

1. 兩數之和

題目：

給定一個整數數組 nums 和一個整數目标值 target，請你在該數組中找出 和為目标值 的那 兩個 整數，并傳回它們的數組下标。

你可以假設每種輸入隻會對應一個答案。但是，數組中同一個元素不能使用兩遍。

你可以按任意順序傳回答案。

示例1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，傳回 [0, 1] 。           

示例2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]           

解法1(暴力解法)

思路：

因為在數組中有兩個整數的和等于目标值，很自然地我們就會想到一個個來嘗試。我們知道目标值target和nums[i]，隻需要找到nums[j]，然後傳回

new int[]{i,j}

即可。

代碼如下：

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        //由于數組中同一個元素不能使用兩遍，是以j從i的下一個元素開始
        for (int j = i + 1; j < nums.length; j++) {
            if (target - nums[i] == nums[j]) {
                return new int[]{i, j};
            }
        }
    }
    return new int[]{};
}           

送出代碼，結果如下：

按道理嵌套循環的話，時間應該會久一點，居然僅用了0ms，我也不太相信，但是送出了三四次也是這個結果，不管了，哈哈~

假如我們想去掉嵌套循環，優化一下，怎麼做呢？沒錯，就是今天的主角，哈希表！

解法2(HashMap)

建立一個Map集合，key是nums[i]元素的值，value是下标值i。當target - 目前周遊的元素的內插補點在map中存在時，就傳回

new int[]{map.get(target-nums[i]),i}

。如果不在map集合中，就把元素值和元素下标存進map集合中。

public int[] twoSum(int[] nums, int target) {
    //map的key是nums[i]的值，value是下标i
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        //擷取結果值與nums[i]的內插補點
        int diff = target - nums[i];
        //如果包含的話，傳回結果
        if (map.containsKey(diff)) {
            return new int[]{map.get(diff), i};
        } else {
            map.put(nums[i], i);
        }
    }
    return new int[]{};
}           

349. 兩個數組的交集

給定兩個數組，編寫一個函數來計算它們的交集。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]           

執行個體2：

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[9,4]           

嵌套循環，比較兩個數組中的元素，如果

nums1[i] == nums2[j]

的話，表示兩個數組中都有的數字，則添加到HashSet(去重)，最後再把HashSet轉換成數組輸出。

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            if (nums1[i] == nums2[j]) {
                set.add(nums1[i]);
            }
        }
    }
    //HashSet轉換成數組輸出
    return set.stream().mapToInt(Integer::intValue).toArray();
}           

經典的擊敗5%的使用者，這是很正常的結果，因為使用了嵌套循環，而且還要把HashSet轉換成數組，非常耗費性能，那麼有沒有優化空間呢，答案是肯定有的。

解法2

如果要判斷一個整數是否包含在無序的數組中，隻能從頭周遊到尾。既然數組在判斷時需要從頭到尾周遊這麼耗費性能，那我們能不能換一種資料結構，做到快速判斷是否包含在其中呢，答案就是哈希表。HashSet的底層就是一個哈希表，是以我們把nums1的數全部存入一個HashSet中，然後再周遊nums2，判斷nums中的元素是否包含在HashSet中即可。

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> s1 = new HashSet<>();
    for (int n1 : nums1) {
        s1.add(n1);
    }
    Set<Integer> s2 = new HashSet<>();
    for (int n2 : nums2) {
        if (s1.contains(n2)) {
            s2.add(n2);
        }
    }
    //把set集合轉成數組，傳回
    int[] res = new int[s2.size()];
    int i = 0;
    for (Integer num : s2) {
        res[i] = num;
        i++;
    }
    return res;
}           

350. 兩個數組的交集II

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2,2]           

輸入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出：[4,9]           

說明：

• 輸出結果中每個元素出現的次數，應與元素在兩個數組中出現次數的最小值一緻。
• 我們可以不考慮輸出結果的順序。

解法1

這道題是上面那道題的變形，不同在于輸出結果不需要去重。是以我們不能使用HashSet存儲，而要改用HashMap，key是數組中的元素，value是元素的個數。在判斷是否包含在其中的時候，還要判斷個數是否大于0，每添加一個元素到結果集中就從HashMap中減去一個元素的個數。

最後把結果集轉成數組傳回即可。

public int[] intersect(int[] nums1, int[] nums2) {
    //key為num1的元素，value為元素出現的次數
    Map<Integer, Integer> map = new HashMap<>();
    for (int num : nums1) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }
    List<Integer> list = new ArrayList<>();
    for (int num : nums2) {
        if (map.containsKey(num) && map.get(num) > 0) {
            list.add(num);
            map.put(num, map.get(num) - 1);
        }
    }
    int[] res = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        res[i] = list.get(i);
    }
    return res;
}           

771. 寶石與石頭

給定字元串J 代表石頭中寶石的類型，和字元串 S代表你擁有的石頭。 S 中每個字元代表了一種你擁有的石頭的類型，你想知道你擁有的石頭中有多少是寶石。

J 中的字母不重複，J 和 S中的所有字元都是字母。字母區分大小寫，是以"a"和"A"是不同類型的石頭。

輸入: J = "aA", S = "aAAbbbb"
輸出: 3           

輸入: J = "z", S = "ZZ"
輸出: 0           

注意:

• S

  和

  J

  最多含有50個字母。

• J

  中的字元不重複。

解法1(HashSet)

這也是一個很典型的使用哈希表判斷是否包含在集合中的題目。思路還是跟前面判斷交集的一樣，先把其中一個字元串周遊每個字元，放進HashSet，然後再周遊另一個字元串，判斷是否包含在其中，包含則數量加一。最後傳回結果。

public int numJewelsInStones(String jewels, String stones) {
    Set<Character> set = new HashSet<>();
    for (char j : jewels.toCharArray()) {
        set.add(j);
    }
    int count = 0;
    for (char s : stones.toCharArray()) {
        if(set.contains(s)){
            count++;
        }
    }
    return count;
}           

解法2(簡化版哈希表)

上面的解法執行用時2ms已經很快了，但是如果細心想一下，其實沒必要使用HashSet集合，因為題目已經告訴我們隻有字母，是以我們大可以使用一個數組模拟一個哈希表，優化一下。

public int numJewelsInStones(String jewels, String stones) {
    //大寫字母'A'的ASCII碼是65，小寫字母'z'的ASCII碼是122
    //是以使用一個長度58的數組已經足夠
    boolean[] bools = new boolean[58];
    for (char j : jewels.toCharArray()) {
        //類似哈希映射，把對應下标标記為true
        bools[j - 'A'] = true;
    }
    int count = 0;
    for (char s : stones.toCharArray()) {
        boolean bool = bools[s - 'A'];
        //如果對應下标為true，則是寶石
        if (bool) {
            count++;
        }
    }
    return count;
}           

387. 字元串中的第一個唯一字元

給定一個字元串，找到它的第一個不重複的字元，并傳回它的索引。如果不存在，則傳回 -1。

示例：

s = "leetcode"
傳回 0

s = "loveleetcode"
傳回 2           

提示：你可以假定該字元串隻包含小寫字母。

解法1(HashMap)

我們可以周遊兩次，第一次周遊使用HashMap記錄字元出現的次數，第二次周遊找出隻出現一次的字元，傳回它的索引。

public int firstUniqChar(String s) {
    Map<Character, Integer> map = new HashMap<>();
    char[] chars = s.toCharArray();
    for (char c : chars) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    for (int i = 0; i < chars.length; i++) {
        Integer count = map.get(chars[i]);
        if (count == 1) {
            return i;
        }
    }
    return -1;
}           

顯然解法1耗時過長，不是很理想。怎麼優化呢，要抓住題目給的提示，隻包含小寫字母。既然隻含有小寫字母，那麼我們就可以簡化哈希表，使用一個數組代替。

public int firstUniqChar(String s) {
    int[] hash = new int[26];
    char[] chars = s.toCharArray();
    for (char ch : chars) {
        hash[ch - 'a']++;
    }
    for (int i = 0; i < chars.length; i++) {
        if (hash[chars[i] - 'a'] == 1) {
            return i;
        }
    }
    return -1;
}           

1365. 有多少小于目前數字的數字

給你一個數組 nums，對于其中每個元素 nums[i]，請你統計數組中比它小的所有數字的數目。

換而言之，對于每個 nums[i] 你必須計算出有效的 j 的數量，其中 j 滿足 j != i 且 nums[j] < nums[i] 。

以數組形式傳回答案。

輸入：nums = [8,1,2,2,3]
輸出：[4,0,1,1,3]
解釋： 
對于 nums[0]=8 存在四個比它小的數字：（1，2，2 和 3）。 
對于 nums[1]=1 不存在比它小的數字。
對于 nums[2]=2 存在一個比它小的數字：（1）。 
對于 nums[3]=2 存在一個比它小的數字：（1）。 
對于 nums[4]=3 存在三個比它小的數字：（1，2 和 2）。           

輸入：nums = [6,5,4,8]
輸出：[2,1,0,3]           

示例3：

輸入：nums = [7,7,7,7]
輸出：[0,0,0,0]           

提示：

• 2 <= nums.length <= 500

• 0 <= nums[i] <= 100

解法1(暴力法)

暴力法思路很簡單粗暴，就是拿每一個元素跟數組中除了自身之外的每一個元素對比，隻要元素大于數組中其他的數就計數加一，最後把計數收集起來就是結果。

public int[] smallerNumbersThanCurrent(int[] nums) {
    int[] res = new int[nums.length];
    int count = 0;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        for (int j = 0; j < nums.length; j++) {
            //排除跟自己對比
            if (i == j) {
                continue;
            }
            //如果元素本身比其他數要大，計數+1
            if (num > nums[j]) {
                count++;
            }
        }
        //收集計數
        res[i] = count;
        //計數器歸0
        count = 0;
    }
    return res;
}           

明顯解法1使用了嵌套循環，導緻耗時太多，結果不太理想。優化代碼前，我們可以先看看提示

0 <= nums[i] <= 100

，也就是說元素的值在0到100範圍内。我們可以使用一個101長度的數組統計元素出現的次數，當我們要計算有多少少于該元素的數字時，就隻需要該元素前面所有元素出現的次數即可。

public int[] smallerNumbersThanCurrent(int[] nums) {
    int[] hash = new int[101];
    //使用數組統計數字出現的次數
    for (int num : nums) {
        //元素值相當于下标，類似于哈希映射
        hash[num]++;
    }
    int[] res = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        //計數
        int count = 0;
        //統計在該元素前的所有元素(也就是小于該元素的數字)出現的次數
        for (int j = nums[i] - 1; j >= 0; j--) {
            //計數器累加，j就是統計哈希表的下标
            count += hash[j];
        }
        res[i] = count;
    }
    return res;
}           

389. 找不同

給定兩個字元串 s 和 t，它們隻包含小寫字母。

字元串 t 由字元串 s 随機重排，然後在随機位置添加一個字母。

請找出在 t 中被添加的字母。

輸入：s = "abcd", t = "abcde"
輸出："e"
解釋：'e' 是那個被添加的字母。           

輸入：s = "", t = "y"
輸出："y"           

輸入：s = "a", t = "aa"
輸出："a"           

• 0 <= s.length <= 1000

• t.length == s.length + 1

• s

  t

  隻包含小寫字母

使用HashMap記錄字元串s中每一個字元出現的次數，然後周遊字元串t，通過字元擷取字元出現的次數，次數大于0就減一，次數等于0則表示是添加的字母，傳回該字母。

public char findTheDifference(String s, String t) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    for (char c : t.toCharArray()) {
        Integer count = map.getOrDefault(c, 0);
        if (count > 0) {
            map.put(c, count - 1);
        } else {
            return c;
        }
    }
    return ' ';
}           

關鍵是抓住提示，字元串s和t隻包含小寫字母，是以我們還是可以使用數組簡化HashMap。小寫字母隻有26個，是以我們建立一個26長度的int數組，統計s字元串中字元出現的次數。其他邏輯和解法1一樣即可。

public char findTheDifference(String s, String t) {
    int[] hash = new int[26];
    for (char c : s.toCharArray()) {
        hash[c - 'a']++;
    }
    for (char c : t.toCharArray()) {
        if (hash[c - 'a'] > 0) {
            hash[c - 'a']--;
        } else {
            return c;
        }
    }
    return ' ';
}           

解法3(排序法)

把兩個字元串轉成字元數組，然後對兩個數組排序。對排序好的數組進行周遊對比，隻要出現不相等的字元，就是要傳回的字元。

public char findTheDifference(String s, String t) {
    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();
    Arrays.sort(sChars);
    Arrays.sort(tChars);
    int length = Math.min(sChars.length, tChars.length);
    int i = 0;
    while (i < length) {
        char sChar = sChars[i];
        char tChar = tChars[i];
        if (sChar != tChar) {
            return tChar;
        }
        i++;
    }
    return tChars[tChars.length - 1];
}           

效率雖然沒有哈希表快，但是也是一種不錯的解題思路。

217. 存在重複元素

給定一個整數數組，判斷是否存在重複元素。

如果存在一值在數組中出現至少兩次，函數傳回

true

。如果數組中每個元素都不相同，則傳回

false

。

輸入: [1,2,3,1]
輸出: true           

輸入: [1,2,3,4]
輸出: false           

輸入: [1,1,1,3,3,4,3,2,4,2]
輸出: true           

假如使用嵌套循環，是會超出時間限制的，是以不能考慮用暴力法。一般來說，判斷一個元素是否包含在其中肯定是HashSet最快，是以我們可以用HashSet容納元素，然後判斷一下是否包含，包含則傳回true，不包含則繼續裝入，如果周遊結束都沒有傳回true，則傳回false。

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (!set.contains(num)) {
            set.add(num);
        } else {
            return true;
        }
    }
    return false;
}           

其實HashSet本身就有去重的效果，我們把所有的元素裝入到HashSet中，如果有重複的元素則長度和原來的長度不相等。

public boolean containsDuplicate(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    return set.size() != nums.length;
}           

409. 最長回文串

給定一個包含大寫字母和小寫字母的字元串，找到通過這些字母構造成的最長的回文串。

在構造過程中，請注意區分大小寫。比如 "Aa" 不能當做一個回文字元串。

假設字元串的長度不會超過 1010。

輸入:
"abccccdd"

輸出:
7

解釋:
我們可以構造的最長的回文串是"dccaccd", 它的長度是 7。           

回文字元串就是從左往右讀和從右往左讀都是一樣的字元串，也就是左右對稱的字元串。要做到左右對稱，其實很簡單，隻要是偶數個相同的字元就可以，比如有兩個"a"，左右兩端各放一個就對稱了。

是以我們用一個HashMap來統計字元出現的次數，然後周遊，判斷如果是偶數就累加字母出現的次數，如果是奇數就減一讓他變成偶數再累加，最後就得到答案res，但是還沒大功告成，因為中點插進一個字母，他還是對稱的，是以最後要判斷一下累加的長度是否等于原來的字元串長度，再決定要不要再加上一個字母的長度。

public int longestPalindrome(String s) {
    HashMap<Character, Integer> map = new HashMap<>();
    //統計字元出現的次數
    for (char c : s.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    int res = 0;
    for (Character key : map.keySet()) {
        Integer val = map.get(key);
        //如果是奇數次，減一成為偶數，再累加
        if (val % 2 != 0) {
            res += (val - 1);
        } else {
            //如果是偶數次，直接累加
            res += val;
        }
    }
    int length = s.length();
    return res == length ? length : (res + 1);
}           

解法2(優化)

題目說明是包含大寫字母和小寫字母，是以我們還是可以使用數組來代替HashMap，以此提高代碼的執行效率。我們隻需要一個長度為128的數組來統計字元出現的次數，代替HashMap。其他邏輯不變即可。

public int longestPalindrome(String s) {
    int[] hash = new int[128];
    for (char c : s.toCharArray()) {
        hash[c - 'A']++;
    }
    int res = 0;
    for (int count : hash) {
        if (count % 2 != 0) {
            res += (count - 1);
        } else {
            res += count;
        }
    }
    int length = s.length();
    return res == length ? length : (res + 1);
}           

204. 計數質數

統計所有小于非負整數

n

的質數的數量。

輸入：n = 10
輸出：4
解釋：小于 10 的質數一共有 4 個, 它們是 2, 3, 5, 7 。           

輸入：n = 0
輸出：0           

輸入：n = 1
輸出：0           

其實這是一個很經典的數學問題，比如要判斷223是不是質數，最粗暴的方法就是，223對(2到222)進行取餘，每次取餘的餘數都不為0，那就是質數。但是如果n的值非常大，那就會超過時間限制。

public int countPrimes(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        //判斷是否是質數，是質數則計數+1
        if (isPrimes(i)) {
            count++;
        }
    }
    return count;
}

//判斷一個數是否是質數
private boolean isPrimes(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2) {
        return true;
    }
    //循環取餘，隻要有一次傳回餘數為0則是非質數
    for (int i = 2; i < num; i++) {
        if (num % i == 0) {
            return false;
        }
    }
    //如果餘數都不為0則是質數
    return true;
}           

不如反向思維一下，我們使用一個boolean[]數組記錄每個數是否是質數，然後從2開始找出非質數都标記成true，标記完成之後就可以統計質數的數量是多少了。

public int countPrimes(int n) {
    boolean[] booleans = new boolean[n];
    for (int i = 2; i < n; i++) {
        for (int j = 2; j * i < n; j++) {
            booleans[i * j] = true;
        }
    }
    int count = 0;
    //從2開始統計
    for (int i = 2; i < booleans.length; i++) {
        if (!booleans[i]) {
            count++;
        }
    }
    return count;
}           

其實上面的代碼還可以優化一下，不需要周遊兩次，把統計和标記放在一個循環即可。代碼如下：

public int countPrimes(int n) {
    int count = 0;
    boolean[] booleans = new boolean[n];
    for (int i = 2; i < n; i++) {
        if (!booleans[i]) {
            for (int j = 2; j * i < n; j++) {
                booleans[i * j] = true;
            }
            count++;
        }
    }
    return count;
}           

解法3

萬萬沒想到，這個題目還有0ms的題解！這是我在送出記錄中一不留神看到的，截圖給大夥看看。

然後我點開代碼一看，好家夥，震驚我一整年！

public int countPrimes(int n) {
    switch (n) {
        case 0: return 0;
        case 1: return 0;
        case 2: return 0;
        case 3: return 1;
        case 4: return 2;
        case 5: return 2;
        case 6: return 3;
        case 7: return 3;
        case 8: return 4;
        case 9: return 4;
        case 10: return 4;
        case 11: return 4;
        case 12: return 5;
        case 13: return 5;
        case 14: return 6;
        case 15: return 6;
        case 10000: return 1229;
        case 499979: return 41537;
        case 999983: return 78497;
        case 1500000: return 114155;
        case 5000000: return 348513;
        default: return -1;
    }
}           

我當然不相信這是能通過的啦，于是複制了這段代碼送出試試，沒想到還真行呀！

總結

哈希表的算法題中有很多問題其實在實際項目中也會遇到，比如找出兩個集合的交集，找出集合中重複的元素等等，是以做一做算法題對我們的編碼能力會有很大的提升。

這篇文章講到這裡了，感謝大家的閱讀，希望看完這篇文章能有所收獲！

覺得有用就點個贊吧，你的點贊是我創作的最大動力~

我是一個努力讓大家記住的程式員。我們下期再見！！！

能力有限，如果有什麼錯誤或者不當之處，請大家批評指正，一起學習交流！