哈希数组

242. Valid Anagram

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, using all the original letters exactly once.

Example 1:

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

Output: true

Example 2:

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

Output: false

Constraints:

  • 1 <= s.length, t.length <= 5 * 10^4
  • s and t consist of lowercase English letters.

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

思路

先判断两个字符串长度是否相等，然后使用哈希数组存储出现过的字母，一增一减，判断数组中元素是否全为0即可。

C++解法

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length() != t.length()){
            return false;
        }
        int hash[26] = {0};
        int i = 0;
        while(s[i] != '\0')
        {
            hash[s[i] - 'a']++;
            i++;
        }
        i = 0;
        while(t[i] != '\0')
        {
            hash[t[i] - 'a']--;
            i++;
        }
        for(int i = 0; i < 26; i++)
        {
            if(hash[i] != 0)
                return false;
        }
        return true;
    }
};

Java解法

以下是修改后的代码：

class Solution {
    public boolean isAnagram(String s, String t) {
        // 检查两个字符串的长度是否相同
        if (s.length() != t.length()) {
            return false;
        }

        // 创建一个大小为26的数组来计数
        int[] chars = new int[26];

        // 遍历第一个字符串，增加字符计数
        for (char ch : s.toCharArray()) {
            chars[ch - 'a']++;
        }

        // 遍历第二个字符串，减少字符计数
        for (char ch : t.toCharArray()) {
            chars[ch - 'a']--;
        }

        // 检查所有计数是否都为0
        for (int count : chars) {
            if (count != 0) {
                return false;
            }
        }

        return true;
    }
}

说明：

  1. 长度检查: 首先检查两个字符串的长度，如果不同，直接返回false。
  2. 使用数组: 使用int[] chars = new int[26];来记录每个字母的计数，避免了动态大小带来的问题。
  3. 更新字符计数: 第一个字符串的字符计数增加，第二个字符串的字符计数减少，以便最终检查结果。
  4. 检查计数: 最后检查计数数组，如果所有元素都是0，则两个字符串是异位词。

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]

Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]

Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints:

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.

思路

方法一：遍历，截取子字符串，判断是否是anagram。这种方式效率低下。

方法二：滑动数组

C++解法

方法二：滑动数组

For 2 strings to be anagrams of each other, they should have the same elements with the same frequency.

vector<int> findAnagrams(string s, string p) {
        int s_len = s.length();
        int p_len = p.length();
        
        if(s.size() < p.size()) return {};
        
        vector<int> freq_p(26,0);
        vector<int> window(26,0);
        
        //first window
        for(int i=0;i<p_len;i++){
            freq_p[p[i]-'a']++;
            window[s[i]-'a']++;
        }
        
        vector<int> ans;
        if(freq_p == window) ans.push_back(0);
        
        for(int i=p_len;i<s_len;i++){
            window[s[i-p_len] - 'a']--;
            window[s[i] - 'a']++;
            
            if(freq_p == window) ans.push_back(i-p_len+1);
        }
        return ans;
    }

**Time Complexity = O(n * 26) = O(n), n is the length of string s.

Space Complexity = O(26) = O(1)

这段 C++ 代码用于找到字符串 s 中所有与字符串 p 由字符组成的所有不同的字母异位词（anagrams）。下面是代码的详细解释：

代码结构解析

  1. 定义函数和参数：

    vector<int> findAnagrams(string s, string p) {

    这里定义了一个函数 findAnagrams，接收两个字符串 s 和 p，返回一个 vector<int> 结果，表示 s 中所有 p 的异位词的起始索引。

  2. 获取字符串长度并进行初步检查：

    int s_len = s.length();
int p_len = p.length();

if(s.size() < p.size()) return {};
    • s_len 和 p_len 分别存储字符串 s 和 p 的长度。
    • 如果 s 的长度小于 p 的长度，则 s 中不可能包含 p 的异位词，函数直接返回一个空的 vector。

  3. 初始化频率数组：

    vector<int> freq_p(26,0);
vector<int> window(26,0);
    • freq_p 用于存储字符串 p 中各个字符的频率。
    • window 用于记录当前窗口（即 s 中的一个子串）内各个字符的频率。

  4. 计算第一个窗口的字符频率：

    for(int i=0;i<p_len;i++){
    freq_p[p[i]-'a']++;
    window[s[i]-'a']++;
}
    • 遍历 p 和 s 的前 p_len 个字符，更新 freq_p 和 window 中各个字符的频率。
    • p[i] - 'a' 计算出字符 p[i] 对应的数组索引（以 a 为起始索引）。

  5. 检查第一个窗口：

    vector<int> ans;
if(freq_p == window) ans.push_back(0);
    • 如果 freq_p 和 window 相等，则说明第一个窗口是 p 的一个异位词，索引 0 被加入到结果 ans 中。

  6. 滑动窗口：

    for(int i=p_len;i<s_len;i++){
    window[s[i-p_len] - 'a']--;
    window[s[i] - 'a']++;
    
    if(freq_p == window) ans.push_back(i-p_len+1);
}
    • 从 p_len 开始，遍历 s 的后续字符。
    • 每次滑动窗口时，移除左侧字符 s[i - p_len] 的频率 (因为这个字符不再在窗口中)，并 增加右侧字符 s[i] 的频率。
    • 在每次滑动后，检查 freq_p 和 window 是否相等，如果相等，则将当前窗口的起始索引 ( i - p_len + 1) 加入 ans 中。

  7. 返回结果：

    return ans;
    • 函数返回所有找到的索引的 vector。

总结

这段代码使用了一个滑动窗口的技术，通过维护两个频率数组（一个用于 p 的字符频率，另一个用于 s 中当前窗口的字符频率）来高效地查找字符串 s 中所有 p 的异位词。每次窗口滑动时，只需更新频率数组，而不需要重新计算整个窗口的字符频率，从而提升了效率。整体时间复杂度为 O(n)，其中 n 是字符串 s 的长度。

Java解法

方法一：

class Solution {  
    public List<Integer> findAnagrams(String s, String p) {  
        List<Integer> result = new ArrayList<>();  
        int pLength = p.length();  
        int sLength = s.length();  
        
        // 仅当s的长度大于或等于p的长度时才处理  
        if (sLength < pLength) return result;  

        for (int i = 0; i <= sLength - pLength; i++) { // 修改为 <= 确保包含最后一个可能的起点  
            String temp = s.substring(i, i + pLength); // 修正这一行  
            if (isAnagram(temp, p)) {  
                result.add(i);  
            }  
        }  
        return result;  
    }  
    
    public boolean isAnagram(String s, String t) {  
        // 检查两个字符串的长度是否相同  
        if (s.length() != t.length()) {  
            return false;  
        }  

        // 创建一个大小为26的数组来计数  
        int[] chars = new int[26];  

        // 遍历第一个字符串，增加字符计数  
        for (char ch : s.toCharArray()) {  
            chars[ch - 'a']++;  
        }  

        // 遍历第二个字符串，减少字符计数  
        for (char ch : t.toCharArray()) {  
            chars[ch - 'a']--;  
        }  

        // 检查所有计数是否都为0  
        for (int count : chars) {  
            if (count != 0) {  
                return false;  
            }  
        }  

        return true;  
    }  
}

2273. Find Resultant Array After Removing Anagrams

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

Example 1:

Input: words = ["abba","baba","bbaa","cd","cd"]
Output: ["abba","cd"]
Explanation:

One of the ways we can obtain the resultant array is by using the following operations:
- Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","baba","cd","cd"].
- Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1].
  Now words = ["abba","cd","cd"].
- Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","cd"].
We can no longer perform any operations, so ["abba","cd"] is the final answer.

Example 2:

Input: words = ["a","b","c","d","e"]
Output: ["a","b","c","d","e"]
Explanation:

No two adjacent strings in words are anagrams of each other, so no operations are performed.

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.

思路

方法一：设定prev=""，每个新元素都排序后转为字符串，然后和prev比较，不相同则加入结果集中

方法二：使用栈

C++解法

class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        for(int i = 1;i<words.size();i++){
            string x = words[i];
            sort(x.begin(),x.end());
            string y = words[i-1];
            sort(y.begin(),y.end());
            if(x == y){
                words.erase(words.begin() + i);
                i--;
            }
        }
        return words;
    }
};

Java解法

方法一完整测试代码：

import java.util.*;

class Solution {
    public List<String> removeAnagrams(String[] words) {
        String prev = "";
        List<String> li = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            char[] ch = words[i].toCharArray();
            Arrays.sort(ch);
            //System.out.println("ch: " + Arrays.toString(ch));
            String curr = String.valueOf(ch);
            //System.out.println("curr: " + curr);
            if (!curr.equals(prev)) {
                li.add(words[i]);
                prev = curr;
            }
        }
        return li;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        String[] words1 = {"abba", "baba", "bbaa", "cd", "cd"};
        System.out.println("Input: " + Arrays.toString(words1));
        List<String> output = solution.removeAnagrams(words1);
        System.out.println("Output: " + output);
    }
}

使用栈的解法如下所示：

class Solution {
    public List<String> removeAnagrams(String[] words) {
        Stack<String> stack = new Stack<>();
        for(int i = words.length-1;i>= 0;i--){
            String s = words[i];
            while(!stack.isEmpty() && anagram(stack.peek(),s) == true)stack.pop();
            stack.push(s);
        }
        List<String> res = new ArrayList<>();
        while(!stack.isEmpty())res.add(stack.pop());
        return res;
    }
    
    public boolean anagram(String p,String q){
        int arr[] = new int[26];
        for(char i : p.toCharArray())arr[i-'a']+=1;
        for(char i : q.toCharArray())arr[i-'a']-=1;
        for(int i : arr)if(i != 0)return false;
        return true;
    }
}

268. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

  • n == nums.length
  • 1 <= n <= 10^4
  • 0 <= nums[i] <= n
  • All the numbers of nums are unique.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

思路

用哈希数组判断数字是否出现过

C++解法

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        vector<int> result(10001, 0);
        int maxValue = -1;
        for(int num : nums){
            result[num]++;
            if(num > maxValue){
                maxValue = num;
            }
        }
        for(int i = 0; i < maxValue; i++){
            if(result[i] == 0){
                return i;
            }
        }
        return maxValue + 1;
    }
};

287. Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and using only constant extra space.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

Constraints:

  • 1 <= n <= 10^5
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

  • How can we prove that at least one duplicate number must exist in nums?
  • Can you solve the problem in linear runtime complexity?

思路

设置一个哈希数组，遍历nums数组，设置哈希数组，如果某个数的频率大于1，则直接结束循环

C++解法

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        vector<int> result(100001, 0);
        for(int num : nums){
            result[num]++;
            if(result[num] > 1){
                return num;
            }
        }
        return -1;
    }
};

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()
    }
}
}

350. Intersection of Two Arrays II

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

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

Example 2:

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

Constraints:

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

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1's size is small compared to nums2's size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

思路

因为0 <= nums1[i], nums2[i] <= 1000，所以这里可以使用哈希数组。对于每一个共同元素，计算其次数然后向结果中添加相应数量的元素。

C++解法

class Solution {
public:
    vector<int> intersect(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){
                int times = min(hash1[i], hash2[i]);
                for(int time = 0; time < times; time++){
                    result.push_back(i);
                }
            }
        }
        return result;
    }
};

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

Constraints:

  • 1 <= ransomNote.length, magazine.length <= 10^5
  • ransomNote and magazine consist of lowercase English letters.

思路

使用哈希数组存储可用的数字，使用magazine字符串存储字符，使用ransomNote字符串消耗字符，不够消耗时，返回false。否则返回true。

C++解法

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        //add
        if (ransomNote.size() > magazine.size()) {
            return false;
        }
        for (int i = 0; i < magazine.length(); i++) {
            // 通过record数据记录 magazine里各个字符出现次数
            record[magazine[i]-'a'] ++;
        }
        for (int j = 0; j < ransomNote.length(); j++) {
            // 遍历ransomNote，在record里对应的字符个数做--操作
            record[ransomNote[j]-'a']--;
            // 如果小于零说明ransomNote里出现的字符，magazine没有
            if(record[ransomNote[j]-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

Java解法

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        // 定义一个哈希映射数组
        int[] record = new int[26];

        // 遍历
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }

        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        
        // 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }

        return true;
    }
}

2215. Find the Difference of Two Arrays

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

  • answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
  • answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:

For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

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

For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Constraints:

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

思路

注意到-1000 <= nums1[i], nums2[i] <= 1000，这里的哈希数组容量及数值需要调整。然后遍历两个哈希数组，找只在一个哈希数组中出现的元素即可。

C++解法

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> result;
        int hash1[2001] = {0};
        int hash2[2001] = {0};
        for(int num : nums1){
            hash1[num + 1000]++;
        }
        for(int num : nums2){
            hash2[num + 1000]++;
        }
        vector<int> temp1;
        vector<int> temp2;
        for(int i = 0; i < 2001; i++){
            if(hash1[i] > 0 && hash2[i] == 0){
                temp1.push_back(i-1000);
            }else if(hash1[i] == 0 && hash2[i] > 0){
                temp2.push_back(i-1000);
            }
        }
        result.push_back(temp1);
        result.push_back(temp2);
        return result;
    }
};

2248. Intersection of Multiple Arrays

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.

Example 1:

Input: nums = [[**3**,1,2,**4**,5],[1,2,**3**,**4**],[**3**,**4**,5,6]]
Output: [3,4]
Explanation: The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= sum(nums[i].length) <= 1000
  • 1 <= nums[i][j] <= 1000
  • All the values of nums[i] are unique.

思路

用哈希数组保存元素出现次数，向结果中加入出现次数等于二维数组长度的元素

C++解法

class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        vector<int> result;
        int hash[1001] = {0};
        // 统计每个数字出现的次数  
        for (int i = 0; i < nums.size(); i++) {  
            for (int j = 0; j < nums[i].size(); j++) {  
                hash[nums[i][j]]++;  
            }  
        }  
        
        // 记录出现次数等于子数组数量的元素  
        for (int i = 0; i < 1001; i++) {  
            if (hash[i] == nums.size()) {
                result.push_back(i);  
            }  
        }  
        return result;
    }
};