# LC 3132. Find the Integer Added to Array II

### [Problem link](https://leetcode.com/problems/find-the-integer-added-to-array-ii/)

###### tags: `leedcode` `medium` `c++`

You are given two integer arrays <code>nums1</code> and <code>nums2</code>.

From <code>nums1</code> two elements have been removed, and all other elements have been increased (or decreased in the case of negative) by an integer, represented by the variable <code>x</code>.

As a result, <code>nums1</code> becomes **equal** to <code>nums2</code>. Two arrays are considered **equal** when they contain the same integers with the same frequencies.

Return the **minimum** possible integer <code>x</code> that achieves this equivalence.

**Example 1:**
Input: nums1 = [4,20,16,12,8], nums2 = [14,18,10]

Output: -2

Explanation:

After removing elements at indices <code>[0,4]</code> and adding -2, <code>nums1</code> becomes <code>[18,14,10]</code>.

**Example 2:**

Input: nums1 = [3,5,5,3], nums2 = [7,7]

Output: 2

Explanation:

After removing elements at indices <code>[0,3]</code> and adding 2, <code>nums1</code> becomes <code>[7,7]</code>.

**Constraints:**

- <code>3 <= nums1.length <= 200</code>
- <code>nums2.length == nums1.length - 2</code>
- <code>0 <= nums1[i], nums2[i] <= 1000</code>
- The test cases are generated in a way that there is an integer <code>x</code> such that <code>nums1</code> can become equal to <code>nums2</code> by removing two elements and adding <code>x</code> to each element of <code>nums1</code>.

## Solution 1
#### C++

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        for (int idx1 = 2; idx1 >= 0; idx1--) {
            int diff = nums2[0] - nums1[idx1];
            int idx2 = 0;  // idx of nums2
            for (int j = idx1; j < nums1.size(); j++) {
                if (nums1[j] + diff == nums2[idx2]) {
                    idx2++;
                    if (idx2 == nums2.size()) {
                        return diff;
                    }                
                }
            }
        }
        return -1;
    }
};

>### Complexity
>n = nums1.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(nlogn) | O(1) |

## Note
sol1:
將num1 與 num2排序過後, num1刪除兩個元素後的第一個元素一定在原本num1的第0個, 第1個或第2個中, 那就拿這三個當頭, 去尋找後續的數組中存不存在subarray == num2.

那因為num1已經排序過, 所以從第2個元素當開頭讓diff最小, 如果第二個元素當頭後有subarray == num2, 那就直接return.
[yt 解說](https://www.youtube.com/watch?v=8tIcs3Zha9M)