本篇同步發布於Blog:[解題] LeetCode - 350 Intersection of Two Arrays II

平台：

LeetCode

題號：

350 - Intersection of Two Arrays II

題目連結：

https://leetcode.com/problems/intersection-of-two-arrays-ii/

題目說明：

        輸入2個陣列nums1和nums2，求這2個陣列有交集的元素。

比如範例輸入的nums1 = [1,2,2,1], nums2 = [2,2]，元素有2個2都出現，所以要回傳[2, 2]。

解題方法：

   　對此2個陣列都從小到大排序，建立兩個指標i和j各自從nums1和nums2的最小值往上比對：

• 如果目前指標指向的值一樣，代表是交集的元素，加入答案，i和j都遞增
• 如果目前指標指向的值nums1[i] > nums2[j]，代表nums2更後面的值要拿來與nums1比對，所以只有j遞增
• 如果目前指標指向的值nums1[i] < nums2[j]，代表nums1更後面的值要拿來與nums2比對，所以只有i遞增

最終i和j有超過nums1/nums2的長度就結束。

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> ans;
        for(int i = 0, j = 0;i < nums1.size() && j < nums2.size();){
            if(nums1[i] == nums2[j]){
                ans.push_back(nums1[i]);
                i++;
                j++;
            }
            else if(nums1[i] > nums2[j]){
                j++;
            }
            else{
                i++;
            }
        }
        
        return ans;
    }
};

int main() {
	Solution sol;
	vector<int> nums1{1,2,2,1};
	vector<int> nums2{2,2};
	vector<int> ans = sol.intersect(nums1, nums2);
	for(int num : ans){
		cout << num << " ";
	}
	return 0;
}

using System;
using System.Linq;
using System.Collections.Generic;

namespace LeetCode350
{
	public class Program
	{
		public class Solution {
		    public int[] Intersect(int[] nums1, int[] nums2) {
		        Array.Sort(nums1);
		        Array.Sort(nums2);
		        List<int> ans = new List<int>();
		        for(int i = 0, j = 0;i < nums1.Length && j < nums2.Length;){
		            if(nums1[i] == nums2[j]){
		                ans.Add(nums1[i]);
		                i++;
		                j++;
		            }
		            else if(nums1[i] > nums2[j]){
		                j++;
		            }
		            else{
		                i++;
		            }
		        }
		        
		        return ans.ToArray();
		    }
		}
		
		public static void Main()
		{
			Solution sol = new Solution();
			int[] nums1 = new int[]{1,2,2,1};
			int[] nums2 = new int[]{2,2};
			var ans = sol.Intersect(nums1, nums2);
			foreach(int num in ans){
				Console.Write(" " + num);
			}
			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/300-399/350.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/300-399/350.cs