Post

Leetcode Day 5 - Hash Table Basics

Covers the basics of hash table usage, including checking for anagrams, finding intersections of arrays, identifying happy numbers, and solving the classic two-sum problem. Focus is on efficient lookup and counting with hash tables.

Posted Updated
By Le Lyu
views 5 min read

Hash Table 1

Link to note about hash table

DiffProblemPythonJava
Easy242 Valid Anagram✅ 
Easy349 Intersection of Two Arrays✅ 
Easy202 Happy Number✅ 
Easy1 Two Sum✅ 

Valid Anagram

Link to Leetcode question2

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1

1
2

Input: s = "anagram", t = "nagaram"
Output: true

Example 2

1
2

Input: s = "rat", t = "car"
Output: false

Solution3

Python

Solution 1: Implement a hash table to record the number of each letter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

  class Solution(object):
    def isAnagram(self, s, t):        
        record = [0] * 26

        for c in s:
            record[ord(c) - ord('a')] += 1
        
        for c in t:
            record[ord(c) - ord('a')] -= 1
        
        for i in range(len(record)):
            if (record[i] != 0):
                return False
        
        return True

Solution 2: Use Counter to count number of each letter exist in each string.

1
2
3
4
5
6

  class Solution(object):
      def isAnagram(self, s, t):        
          from collections import Counter
          a = Counter(s)
          b = Counter(t)
          return a == b

Similar Questions

DiffSimilar QuestionsPythonJava
Easy2273 Find Resultant Array After Removing Anagrams4  
Medium49 Group Anagrams5  
Medium438. Find All Anagrams in a String6  

Intersection of Two Arrays

Link to Leetcode question7

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1

1
2

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2

1
2
3

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Solution8

Python

Solution 1: Use dictionary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  class Solution(object):
    def intersection(self, nums1, nums2):
        from collections import Counter
        record = {-1:-1}
        intersection = []
        
        for num in nums1:
            record[num] = num
        
        for num in nums2:
            try:
                if(record[num] not in intersection):
                    intersection += [record[num]]
            except:
                temp = num

        return intersection

Solution 2: Use set

1
2
3

  class Solution(object):
    def intersection(self, nums1, nums2):
        return list(set(nums1) & set(nums2))

Similar Questions

DiffSimilar QuestionsPythonJava
Easy350 Intersection of Two Arrays II9  
Medium3002 Maximum Size of a Set After Removals10  

Happy Number

Link to Leetcode question11

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

  • Starting with any positive integer, replace the number by the sum of the squares of its digits.
  • Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
  • Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1

1
2
3
4
5
6
7

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Example 2

1
2

Input: n = 2
Output: false

Solution12

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def isHappy(self, n):
        n = str(n)
        record = []

        while(True):
            new_n = 0
            for num in n:
                new_n += int(num) ** 2
            
            if(new_n not in record):
                record += [new_n]
            elif(new_n == 1):
                return True
            else:
                return False
            n = str(new_n)

Similar Questions

DiffSimilar QuestionsPythonJava
Easy263 Ugly Number13  
Medium2457 Minimum Addition to Make Integer Beautiful14  

Two Sum

Link to Leetcode question15

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1

1
2
3

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2

1
2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3

1
2

Input: nums = [3,3], target = 6
Output: [0,1]

Solution16

Python

Solution 1: Brute Force Time Complexity: O(n2)

1
2
3
4
5
6

  class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if(nums[i]+nums[j] == target):
                    return [i,j]

Solution 2: Use dictionary Time Complexity: O(n)

1
2
3
4
5
6
7
8
9

  class Solution(object):
    def twoSum(self, nums, target):
        records = dict()

        for index, value in enumerate(nums):
            if((target - value) in records):
                return index, records[target - value]
            else:
                records[value] = index

Similar Questions

DiffSimilar QuestionsPythonJava
Medium15 3Sum17  
Medium167. Two Sum II - Input Array Is Sorted[^tsiiiais]  

Reference

  1. 代码随想录-哈希表理论基础: https://programmercarl.com/哈希表理论基础.html#哈希表. ↩︎

  2. Leetcode-242 Valid Anagram: https://leetcode.com/problems/valid-anagram/description/. ↩︎

  3. 代码随想录-有效的字母异位词: https://programmercarl.com/0242.有效的字母异位词.html. ↩︎

  4. Leetcode-2273 Find Resultant Array After Removing Anagrams: https://leetcode.com/problems/find-resultant-array-after-removing-anagrams/description/. ↩︎

  5. Leetcode-49 Group Anagrams: https://leetcode.com/problems/group-anagrams/description/. ↩︎

  6. Leetcode-438 Find All Anagrams in a String: https://leetcode.com/problems/find-all-anagrams-in-a-string/. ↩︎

  7. Leetcode-349 Intersection of Two Arrays: https://leetcode.com/problems/intersection-of-two-arrays/description/. ↩︎

  8. 代码随想录-两个数组的交集: https://programmercarl.com/0349.两个数组的交集.html. ↩︎

  9. Leetcode-350 Intersection of Two Arrays II: https://leetcode.com/problems/intersection-of-two-arrays-ii/description/. ↩︎

  10. Leetcode-3002 Maximum Size of a Set After Removals: https://leetcode.com/problems/maximum-size-of-a-set-after-removals/. ↩︎

  11. Leetcode-202 Happy Number: https://leetcode.com/problems/happy-number/description/. ↩︎

  12. 代码随想录-快乐数: https://programmercarl.com/0202.快乐数.html. ↩︎

  13. Leetcode-263 Ugly Number: https://leetcode.com/problems/ugly-number/description/. ↩︎

  14. Leetcode-2457 Minimum Addition to Make Integer Beautiful: https://leetcode.com/problems/minimum-addition-to-make-integer-beautiful/. ↩︎

  15. Leetcode-1 Two Sum: https://leetcode.com/problems/two-sum/description/. ↩︎

  16. 代码随想录-两数之和: https://programmercarl.com/0001.两数之和.html. ↩︎

  17. Leetcode-15 3Sum: https://leetcode.com/problems/3sum/description/. ↩︎

Data Structure and Algorithm, Leetcode, Hash Table
hash table string sorting double pointers binary search
This post is licensed under CC BY 4.0 by the author.