刷题届的abandon——两数之和

  LeetCode上的第一题：两数之和。

  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

  对于这道题目首先最容易想到的就是使用暴力枚举，通过两两比对两个数的和，看是否为target，代码如下。

vector<int> twoSum(vector<int>& nums, int target)
{
    int n = nums.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if (nums[i] + nums[j] == targer)
            {
                return {i, j};
            }
        }
    }
    return {};
}

  这种情况下，由于两个for循环的嵌套，因此时间复杂度为\(O(n^2)\)。

  看看能不能继续优化。由于在暴力枚举的情况下，绝大多数时间都花费在这个过程中：对于一个数nums[i]，找剩下的数中是否存在一个nums[j]，使得两者和为target。也就是说第二层循环花费了太多的时间。

  为了减少找这个nums[j]所花费的时间，我想到了一种办法——借助桶来实现空间换时间。

  对于个nums[i]，我需要知道在剩下的数字中是否存在一个数为target-nums[i]。如果存在，则我要得到这个数的索引。因此，在开始前可以先遍历一遍整个数组，用一堆桶来标记每个数的索引位置，其中桶的索引就是这个数字，桶中存的数据就是这个数字在数组中的位置。

  但是这样的话还有一个问题。在题目要求中，数组中的数字可以为负数，而桶的索引始终是正数。所以我选择使用一个二维数组来表示这堆桶，0表示负数，1表示正数。

例如：

bucket[0][7] = 2;   // 记录-7在数组中的索引为2
bucket[1][48] = 8;  // 记录48在数组中的索引为8

  在有了这个桶之后，接下来对于每一个数nums[i]就只需要在编号为target-num[i]的桶中查看它的索引就行，若为-1，则表示没有这个需要的数，也就是说在数组中不存在一个数能够使得其与nums[i]的和为target，那就去看下一个数字了。

代码如下：

vector<int> twoSum(vector<int>& nums, int target) 
{
    int bucket[2][10000001];
    memset(bucket, -1, sizeof(bucket));
    int n = nums.size();

    // 获取数组中每个数的坐标信息存在桶中
    for (int i = 0; i < n; i++)
    {
        if (nums[i] < 0)
        {
            bucket[0][-nums[i]] = i;
        }
        else if (nums[i] == 0)
        {
            bucket[0][0] = i;
            bucket[1][0] = i;
        }
        else
        {
            bucket[1][nums[i]] = i;
        }
    }

    int rest;
    for (int i = 0; i < n; i++)
    {
        rest = target - nums[i];
        if (rest < 0)
        {
            if (bucket[0][-rest] != -1 && i != bucket[0][-rest])
            {
                return {i, bucket[0][-rest]};
            }
        }
        else if (rest == 0)
        {
            if (bucket[0][0] != -1 && i != bucket[0][0])
            {
                return {i, bucket[0][0]};
            }
        }
        else
        {
            if (bucket[1][rest] != -1 && i != bucket[1][rest])
            {
                return {i, bucket[1][rest]};
            }
        }
    }

    return {};
}

  这样一来两个for循环都是线性遍历数组，因此算法的时间复杂度为\(O(n)\)。但是还有一个问题，空间开销太大了并且数组范围不够。若测试用例中有数大于了10000000，则会导致数组越界。因此这个算法只能提供一个空间换时间的思想。

  为避免空间开销太大，可以使用cpp中的map容器来代替一个巨大的二维数组。

vector<int> twoSum(vector<int>& nums, int target) 
{
    map<int, int> map;
    int n = nums.size();
    for (int i = 0; i < n; i++)
    {
        map[nums[i]] = i;
    }

    for (int i = 0; i < n; i++)
    {
        if (map.find(target - nums[i]) != map.end() && i != map[target - nums[i]])
        {
            return {i, map[target - nums[i]]};
        }
    }
     return {};
}

  不过上面这个代码还可以继续优化。这两个线性for循环还可以进一步继续压缩为一个for循环。首先先初始化一个空的哈希表，对于数组中的每一个元素查看哈希表中是否存在能与其组成target的数，若不存在则将其索引位置加入哈希表中并查看下一个数。这样一来也不需要i != map[target - nums[i]]的判断了。因为数组里面的所有数只会被遍历一次，并且在遍历到这个数之前，哈希表中必定不存在这个数。

代码如下：

vector<int> twoSum(vector<int>& nums, int target) 
{
    map<int, int> hashtable;
    for (int i = 0; i < nums.size(); i++)
    {
        auto j = hashtable.find(target - nums[i]);
        if (j != hashtable.end())
        {
            return {i, hashtable[target - nums[i]]};
        }
        hashtable[nums[i]] = i;
    }
    return {};
}