Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/349.html

 349	Intersection of Two Arrays

 Given two arrays, write a function to compute their intersection.

 Example:
 Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

 Note:
     Each element in the result must be unique.
     The result can be in any order.

 @tag-array

Algorithm

Use a HashSet to put all nums1 in, and then traverse the elements of nums2. If it exists in the HashSet, it means that it is the intersection part, add it to the HashSet of the result, and finally convert the result to the form of a vector.

Or, use two pointers to do it, first sort the two arrays, then use the two pointers to point to the beginning of the two arrays respectively, then compare the size of the two arrays, move the pointer of the small number backward, if the two pointers point to The numbers are equal, add this number to the result.

Code

• Java
• C++
• Python
• Go
• Javascript

• import java.util.Arrays;
  import java.util.HashSet;
  import java.util.Set;
  
  public class Intersection_of_Two_Arrays {
  
      // Sort both arrays, use two pointers
      // Time complexity: O(nlogn)
      public class Solution {
          public int[] intersection(int[] nums1, int[] nums2) {
              Set<Integer> set = new HashSet<>();
              Arrays.sort(nums1);
              Arrays.sort(nums2);
              int i = 0;
              int j = 0;
              while (i < nums1.length && j < nums2.length) {
                  if (nums1[i] < nums2[j]) {
                      i++;
                  } else if (nums1[i] > nums2[j]) {
                      j++;
                  } else {
                      set.add(nums1[i]);
                      i++;
                      j++;
                  }
              }
              int[] result = new int[set.size()];
              int k = 0;
              for (Integer num : set) {
                  result[k++] = num;
              }
              return result;
          }
      }
  
  
      // Use two hash sets
      // Time complexity: O(n)
      public class Solution_hashset {
          public int[] intersection(int[] nums1, int[] nums2) {
              Set<Integer> set = new HashSet<>();
              Set<Integer> intersect = new HashSet<>();
              for (int i = 0; i < nums1.length; i++) {
                  set.add(nums1[i]);
              }
              for (int i = 0; i < nums2.length; i++) {
                  if (set.contains(nums2[i])) {
                      intersect.add(nums2[i]);
                  }
              }
              int[] result = new int[intersect.size()];
              int i = 0;
              for (Integer num : intersect) {
                  result[i++] = num;
              }
              return result;
          }
      }
  
  }
  
  ############
  
  class Solution {
      public int[] intersection(int[] nums1, int[] nums2) {
          Set<Integer> s = new HashSet<>();
          for (int num : nums1) {
              s.add(num);
          }
          Set<Integer> t = new HashSet<>();
          for (int num : nums2) {
              if (s.contains(num)) {
                  t.add(num);
              }
          }
          int[] res = new int[t.size()];
          int i = 0;
          for (int num : t) {
              res[i++] = num;
          }
          return res;
      }
  }
  

• // OJ: https://leetcode.com/problems/intersection-of-two-arrays/
  // Time: O(A + B)
  // Space: O(A + B)
  class Solution {
  public:
      vector<int> intersection(vector<int>& A, vector<int>& B) {
          unordered_set<int> a(begin(A), end(A)), b(begin(B), end(B));
          vector<int> ans;
          for (int n : a) {
              if (b.count(n)) ans.push_back(n);
          }
          return ans;
      }
  };
  

• class Solution:
      def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
          s = set(nums1)
          res = set()
          for num in nums2:
              if num in s:
                  res.add(num)
          return list(res)
  
  ############
  
  class Solution(object):
    def intersection(self, nums1, nums2):
      """
      :type nums1: List[int]
      :type nums2: List[int]
      :rtype: List[int]
      """
      d = {}
      ans = []
      for num in nums1:
        d[num] = d.get(num, 0) + 1
  
      for num in nums2:
        if num in d:
          ans.append(num)
          del d[num]
      return ans
  
  

• func intersection(nums1 []int, nums2 []int) []int {
  	s := make(map[int]bool)
  	for _, num := range nums1 {
  		s[num] = true
  	}
  	t := make(map[int]bool)
  	var res []int
  	for _, num := range nums2 {
  		if s[num] && !t[num] {
  			res = append(res, num)
  			t[num] = true
  		}
  	}
  	return res
  }
  

• /**
   * @param {number[]} nums1
   * @param {number[]} nums2
   * @return {number[]}
   */
  var intersection = function (nums1, nums2) {
      const s = new Set();
      for (const num of nums1) {
          s.add(num);
      }
      let res = new Set();
      for (const num of nums2) {
          if (s.has(num)) {
              res.add(num);
          }
      }
      return [...res];
  };
  
  

All Problems

All Solutions