哈希集合

• 349. Intersection of Two Arrays
  • 思路
  • C++解法
  • Java解法
  • Python解法
  • Go解法
  • Rust解法
• 202. Happy Number
  • 思路
  • C++解法
  • Java解法

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.

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

思路

方法一：因为0 <= nums1[i], nums2[i] <= 1000，所以这里可以使用哈希数组

方法二：使用Hashset判断元素是否出现并去重

C++解法

方法一：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        int hash1[1001] = {0};
        int hash2[1001] = {0};
        for(int num : nums1){
            hash1[num]++;
        }
        for(int num : nums2){
            hash2[num]++;
        }
        for(int i = 0; i < 1001; i++){
            if(hash1[i] > 0 && hash2[i] > 0){
                result.push_back(i);
            }
        }
        return result;
    }
};

方法二：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重
        unordered_set<int> nums_set(nums1.begin(), nums1.end());
        for (int num : nums2) {
            // 发现nums2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

• 时间复杂度: O(n + m) m 是最后要把 set转成vector
• 空间复杂度: O(n)

Java解法

方法二：

import java.util.*;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> resultSet = new HashSet<>();
        Set<Integer> numsSet = new HashSet<>();

        for (int num : nums1) {
            numsSet.add(num);
        }
        
        for (int num : nums2) {
            if (numsSet.contains(num)) {
                resultSet.add(num);
            }
        }

        return resultSet.stream().mapToInt(Integer::intValue).toArray();
    }
}

Python解法

方法二：

from typing import List

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result_set = set()
        nums_set = set(nums1)

        for num in nums2:
            if num in nums_set:
                result_set.add(num)

        return list(result_set)

Go解法

方法二：

package main

import "fmt"

func intersection(nums1 []int, nums2 []int) []int {
    resultSet := make(map[int]struct{})
    numsSet := make(map[int]struct{})

    for _, num := range nums1 {
        numsSet[num] = struct{}{}
    }

    for _, num := range nums2 {
        if _, exists := numsSet[num]; exists {
            resultSet[num] = struct{}{}
        }
    }

    result := make([]int, 0, len(resultSet))
    for num := range resultSet {
        result = append(result, num)
    }
    
    return result
}

func main() {
    fmt.Println(intersection([]int{1, 2, 2, 1}, []int{2, 2})) // Example usage
}

Rust解法

方法二：

#![allow(unused)]
fn main() {
use std::collections::HashSet;

pub struct Solution;

impl Solution {
    pub fn intersection(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let nums_set: HashSet<i32> = nums1.into_iter().collect();
        let result_set: HashSet<i32> = nums2.into_iter().filter(|num| nums_set.contains(num)).collect();
        
        result_set.into_iter().collect()
    }
}
}

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: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 2
Output: false

Constraints:

• 1 <= n <= 2^31 - 1

思路

判断某个元素是否出现过（是否有循环），使用unordered_set数据结构

这道题目看上去貌似一道数学问题，其实并不是！

题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！

当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。

所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。

判断sum是否重复出现就可以使用unordered_set。

还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

C++解法

class Solution {
public:
    // 取数值各个位上的单数之和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> set;
        while(1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 如果这个sum曾经出现过，说明已经陷入了无限循环了，立刻return false
            if (set.find(sum) != set.end()) {
                return false;
            } else {
                set.insert(sum);
            }
            n = sum;
        }
    }
};

• 时间复杂度: O(logn)
• 空间复杂度: O(logn)

Java解法

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
}