交换和--排序

LeetCode

面试题 16.21.交换和

给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

示例:

输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]

示例:

输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []

提示：

• 1 <= array1.length, array2.length <= 100000

解法：求和取差值

解题思路：

思路很简单，我们先求出两个数组的和num1和num2，然后对两个数组遍历，求出两个元素的差值diff,如果diff*2 == num1-num2,那这两个元素就是我们要求的结果了

我的代码（超时）

class Solution {
    public int[] findSwapValues(int[] array1, int[] array2) {
        int num1 = 0;
        int num2 = 0;
        ArrayList<Integer> arr1 = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();
        for(int i=0; i<array1.length; i++)
        {
            if(i>0)
            {
                if(array1[i]!=array1[i-1])
                    arr1.add(array1[i]);
            }     
            else
                arr1.add(array1[i]);
            num1+=array1[i];
        }
        for(int i=0; i<array2.length; i++)
        {
            if(i>0)
            {
                if(array2[i]!=array2[i-1])
                    arr2.add(array2[i]);
            }   
            else
                arr2.add(array2[i]);
            num2+=array2[i];
        }
        for(int x: arr1)
        {
            for(int y: arr2)
            {
                if(Math.abs(x-y)*2==Math.abs(num1-num2))
                {
                    int[] res = {x,y};
                    return res;
                }
            }
        }
        int[] res = new int[0];
        return res;
    }
}

改进代码：

class Solution {
    public int[] findSwapValues(int[] array1, int[] array2) {
        Arrays.sort(array1);
        Arrays.sort(array2);
        Set<Integer> set = new HashSet<>();
        int sum1=0,sum2=0;
        for(int i:array2) 
        {
            set.add(i);
            sum2+=i;
        }
        for(int i:array1) 
        {
            sum1+=i;
        }
        if((sum1-sum2)%2!=0) return new int[] {};
        int count = (sum1-sum2)/2;
        for(int i=0;i<array1.length;i++) 
        {
            if(set.contains(array1[i]-count)) 
            {
                return new int[] {array1[i],array1[i]-count};
            }
        }
        return new int[] {};
    }
}