Problem: 面试题 16.21. 交换和

题目描述

思路及解法

1.分别求取array1与array2数组每一个元素的和（sum1与sum2）并同时将array2的元素存入一个set集合中；
2.如果sum1和sum2的和为奇数，则不存在；
3.计算sum1与sum2的和的一半，同时减去sum1并用变量diff记录下来；
4.遍历array1同时在set集合中查找是否存在（array1[i] + diff）;若存在则交换array1[i]与array1[i] + diff;

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

class Solution {
public:
    /**
     * Hash
     * @param array1 Given array1
     * @param array2 Given array2
     * @return vector<int>
     */
    vector<int> findSwapValues(vector<int>& array1, vector<int>& array2) {
        int len1 = array1.size();
        int len2 = array2.size();
        //Calculate the sum of array1
        int sum1 = 0;
        for (int i = 0; i < len1; ++i) {
            sum1 += array1[i];
        }
        int sum2 = 0;
        unordered_set<int> set;
        //Evaluates the elements of array2 and
        // stores its elements into the hash collection
        for (int i = 0; i < len2; ++i) {
            sum2 += array2[i];
            if (set.find(array2[i]) == set.end()) {
                set.insert(array2[i]);
            }
        }
        //Does not exist if the sum is odd
        int sum = sum1 + sum2;
        if (sum % 2 != 0) {
            return vector<int>();
        }
        //Iterate over each element in array1,
        // looking it up in the hash table
        int diff = sum / 2 - sum1;
        for (int i = 0; i < len1; ++i) {
            int target = array1[i] + diff;
            if (set.find(target) != set.end()) {
                return vector<int>{array1[i], target};
            }
        }
        return vector<int>();
    }
};