LeetCode 3132. 找出与数组相加的整数 II （双指针、枚举）_leetcode3132

题目：3132. 找出与数组相加的整数 II

思路：先将两个数组升序排序，然后在nums1中选取前三个元素中的一个nums1[i]作为最后留下的数，就可以得到x，最后比对即可。细节看注释
原理是前三个元素中的一个肯定是会留下来的。

class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
    	//将两个数组升序排序
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        //保存最小的x
        int tmp=INT_MAX;
        //在nums1中选取前三个元素中的一个nums1[i]作为最后留下的数
        for(int i=0;i<3;i++){
        	//得到x
            int x=nums2[0]-nums1[i];
            //记录匹配过程中，nums1数组中不和nums2数组元素匹配的个数
            int ans=0;
            int j=0;
            int k=0;
            while(1){
                if(k==nums1.size()||j==nums2.size()){
                    break;
                }
                if(x+nums1[k]!=nums2[j]) ans++;
                else j++;
                k++;
            }
            //如果是k先达到，那就是看ans和剩下未匹配的nums2的数量之和是否==ans
            //如果是j先达到，那就是看ans和剩下未匹配的nums1的数量之和是否==ans
            if(k==nums1.size()&&nums2.size()-j+ans==2||j==nums2.size()&&nums1.size()-k+ans==2){
                tmp=min(tmp,x);
            }
        }
        return tmp;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33