Question

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

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

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

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;
    }
};

'''
https://docs.python.org/3/reference/expressions.html#operator-precedence

high to low:

**

*, @, /, //, %

+, -

<<, >>

&

^

|

in, not in, is, is not, <, <=, >, >=, !=, ==

and

or

if – else


'''
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)

# no extra space
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        ans = []
        nums1.sort()
        nums2.sort()
        i = j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                # ans.append(nums1[i]) # for Leetcode 350, input with duplicates
                if (not ans) or (len(ans) > 0 and ans[-1] != nums1[i]):
                    ans.append(nums1[i])
                i += 1
                j += 1

        return ans

############

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];
};

class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersection($nums1, $nums2) {
        $rs = [];
        $set1 = array_values(array_unique($nums1));
        $set2 = array_values(array_unique($nums2));
        for ($i = 0; $i < count($set1); $i++) {
            $hashmap[$set1[$i]] = 1;
        }
        for ($j = 0; $j < count($set2); $j++) {
            if ($hashmap[$set2[$j]]) array_push($rs, $set2[$j]);
        }
        return $rs;
    }
}

349 - Intersection of Two Arrays

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions