每天算法 -- 两数和 - easy

Google:

Given a list of numbers and a number k, return whether any two numbers from the list add up to k

For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

Bonus: Can you do this in one pass?

这是谷歌很经典的一道题，在数组中寻找两个数，它们的和是否为k.

基本上所有的算法题，都有一个暴力解。我们就先从暴力解法开始。

注意：笔者会尽量使用新的C++语法来描述算法，而不是类C的代码风格。

Solution 1 暴力法:

#include <iostream>
#include <vector>
#include <algorithm>

bool TwoSum(std::vector<int> data, int k)
{
    int index = 1;
    auto iterFind = std::find_if(data.begin(), data.end(), [=, &index](int val){
        int leftSum = k - val;
        auto iter = std::find(data.begin() + index, data.end(), leftSum);
        index ++;
        if(iter != data.end())
        {
            return true;
        }
    });

    if(iterFind != data.end())
    {
        return true;
    }
    else
    {
        return false;
    }   
}

分析：对于给定数组中的每一个元素，每一次都要将其与k的差值与其后的所有元素比较。即，(n-1) + (n-2) + ... + 0, 这个和用算法复杂来描述是.

注意，在暴力法当中，这里有个小小的优化，每个数N, 它的K-N只与后面的所有数相比较，避免了重复的比较。相对于K-N与其余所有其它数比较而言。

Solution 2, 排序 + 二分查找

排序往往可以作为解算法题的一个突破口，那么假定数据是有序的，会有什么变化发生呢？

对于K-N我们是不是可以使用二分来查找对应的元素呢？

bool TwoSumSortAndBinarySearch(std::vector<int> data, int k)
{
    std::sort(data.begin(), data.end());
    int index = 1;
    auto iterFind = std::find_if(data.begin(), data.end(), [=, &index](int val)
    {
        int leftSum = k -val;
        bool isFound = std::binary_search(data.begin() + index, data.end(), leftSum);
        index++;
        return isFound;
    });
    if(iterFind != data.end())
    {
        return true;
    }
    else
    {
        return false;
    }
}

std::sort的排序复杂度是在, 而对于每一个元素进行二分查找的效率是，则可以得之，上述算法的复杂度是在

Solution 3 排序 + 前后逼近

在数据基本有序的情况下，设置两个指针，一个指向第一个元素，另一个指向最后一个元素。若两个之和小于K, 说明第一个数字太小了，必须要换成更大的数字，那第一个指针后移; 若大于K，第二个指针前移; 若两数和刚好相同，则返回为真。若两个指针指向同一位置，说明已经遍历完有意义的和了。

这样一来，就从变成了，

bool TwoSumSortAndFrondEndEnclose(std::vector<int> data, int k)
{
    std::sort(data.begin(), data.end());
    auto front = data.begin();
    auto end = data.end() - 1;
    while(front != end)
    {
        if(*front + *end == k)
        {
            return true;
        }
        else if (*front + *end < k)
        {
            front++;
        }
        else if(*front + *end > k)
        {
            end--;
        }
    }
    return false;
}

算法复杂度分析，这个算法主要的复杂度依赖于排序算法的效率，也即

Solution 4 Hash表

最后，是最经典的算法，真正意义上的

用一个哈希表存储，过程中元素的K-N

对于每个元素，首先在哈希表当中查找，若找到，则说明已经匹配到，若没有，则将它与K的差值，K-N存储在哈希表当中。留待后来的元素判断是否与之相等。

bool TwoSumOnePassBySet(std::vector<int> data, int k)
{
    std::unordered_set<int> leftSums;
    auto iter = std::find_if(data.begin(), data.end(), [&leftSums, k](int val)
    {
        int leftSum = k - val;
        bool ret = false;
        if(leftSums.find(val) != leftSums.end())
        {
            ret = true;
        }
        else
        {
            ret = false;
        }
        
        leftSums.insert(leftSum);
        return ret;
    });
    return (iter != data.end() ? true : false);
}

int main()
{
    std::vector<int> data1 = {1, 3, 5, 8, 9};
    std::vector<int> sums = {4, 1, 2, 8, 17, 0, -1, 3};
    
    std::for_each(data1.begin(), data1.end(), [](int val){
        std::cout << val << " ";
    });
    std::cout << std::endl;

    for(auto sum : sums)
    {
        std::cout << "Sum: " << sum << "t";
        std::cout << TwoSumBruteForce(data1, sum) << "t" << 
            TwoSumSortAndBinarySearch(data1, sum) << "t" <<
            TwoSumSortAndFrondEndEnclose(data1, sum) << "t" <<
            TwoSumOnePassBySet(data1, sum) << std::endl;
    }

    return 0;
}

算法执行的测试结果如下：

1 3 5 8 9 
Sum: 4	1	1	1	1
Sum: 1	0	0	0	0
Sum: 2	0	0	0	0
Sum: 8	1	1	1	1
Sum: 17	1	1	1	1
Sum: 0	0	0	0	0
Sum: -1	0	0	0	0
Sum: 3	0	0	0	0

最后

以上就是还单身斑马为你收集整理的每天算法 -- 两数和 - easy的全部内容，希望文章能够帮你解决每天算法 -- 两数和 - easy所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。