代码随想录：哈希表

代码随想录-哈希表篇

在大学或者其他时候学习数据结构课程时。不难发现，算法发展都是由于对时间或者空间有较高的需求，从而一步步优化。在查询优化时，到二分法( log(N) )时，开始出现了瓶颈， 如何降到O(1)或者退而求其次追求O(2),O(3)呢？

在顺序查找和二分查找时，我们都是索引+关键字存储,那能不能直接使用关键字充当索引，那不就能直接O（1）了吗？

哈希表就是怎么个思想（个人这样想的）

要深入学习的话，可以考虑由这些方面入手：空间开辟大小、哈希函数（存储）、解决哈希冲突、底层原理等。

嘛，这里主要是入门一下，通过做题感受一下

242.有效的字母异位词

力扣题目链接(opens new window)

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

这个题目给出的都是小写字母，所以在用go写的方法里面就更简单一些。额也因为Java写的不太好

class Solution {
       public boolean isAnagram(String s, String t) {
           HashMap<Character,Integer>map=new HashMap<>();
           for(int i=0;i<s.length();i++) {
               Character temp=s.charAt(i);
               if(!map.containsKey(temp)){
                   map.put(temp,1);
               }else {
                   map.put(temp, map.get(temp)+1);
               }
           }
           for(int i=0;i<t.length();i++) {
               Character temp=t.charAt(i);
               if(!map.containsKey(temp)){
                  return false;
               }else {
                   map.put(temp, map.get(temp)-1);
               }
           }
           for (Integer value : map.values()) {
               if(value!=0){
                   return false;
               }
           }
           return true;
       }
   }

func isAnagram(s string, t string) bool {
    if len(s)!=len(t){
        return false
    }
    arrays :=[26]int{}
    for _,val :=range s {
        arrays[val-rune('a')]++
    }
    for _,val :=range t {
        arrays[val-rune('a')]--
    }
    return arrays==[26]int{}
}

349. Intersection of Two Arrays

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:

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

Example 2:

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

class Solution {
     public int[] intersection(int[] nums1, int[] nums2) {
         if(nums1.length==0||nums1==null||nums2==null||nums2.length==0){
             return new int[]{};
         }
        HashSet<Integer>set1=new HashSet<>();
        HashSet<Integer>set2=new HashSet<>();

         for (int i : nums1) {
             set1.add(i);
         }
         for (int i : nums2) {
             if(set1.contains(i)){
                 set2.add(i);
             }
         }
         return set2.stream().mapToInt(x->x).toArray();
     }
 }

func intersection(nums1 []int, nums2 []int) []int {

	if len(nums1) == 0 || nums1 == nil || len(nums2) == 0 || nums2 == nil {
		return nil
	}
	set := make(map[int]struct{})
	res := make([]int, 0)

	for _, v := range nums1 {
		if _,ok := set[v];!ok{
			set[v] = struct{}{}
		}
	}
	for _,v := range nums2 {
		if _, ok := set[v]; ok {
			res = append(res, v)
			delete(set, v)
		}
	}
	return res
}

202. Happy Number

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:

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

Example 2:

Input: n = 2
Output: false

func isHappy(n int) bool {
	set := make(map[int]bool)
	for n!=1 && !set[n] {
        n,set[n] =getSum(n),true
	}
    return n==1
}

func getSum(n int) int {
	sum := 0
	for n != 0 {
		sum+=(n%10)*(n%10)
		n=n/10
	}
	return sum
}

1. Two Sum

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:

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

Example 2:

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

Example 3:

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

func twoSum(nums []int, target int) []int {
	set := make(map[int]int)
	for index, val := range nums {
		if preIndex, ok := set[target-val]; ok {
                // 第一轮主要是去重，防止覆盖
				return []int{preIndex, index}
		} else {
			// 数组值为map的key，下标为map的值
			set[val] = index
		}
	}
	return nil
}

454. 4Sum II

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

func fourSumCount(nums1 []int, nums2 []int, nums3 []int, nums4 []int) int {
	count := 0
	hashmap := make(map[int]int)
	n := len(nums1)

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			// key放和，val放出现次数
			hashmap[nums1[i]+nums2[j]]++
		}
	}
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			count += hashmap[0-(nums3[i]+nums4[j])]
		}
	}
	return count
}

383. Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

func canConstruct(ransomNote string, magazine string) bool {
	strMap := make(map[int]int)

	for i := range magazine {
		strMap[int(magazine[i])]++
	}
	for i := range ransomNote {
		if strMap[int(ransomNote[i])]==0{
            
			return false
		}
        strMap[int(ransomNote[i])]--
	}
	return true
}