LeetCode 算法题 1. 两数之和

分类：algorithm| 发布时间：2016-06-23 12:40:00

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9,

因为 nums[0] + nums[1] = 2 + 7 = 9,
所以返回 [0, 1].

思路

首先想到就是通过哈希表（hash_table）来记录需要的数值与下标的对应关系。按顺序扫描数组，查找 hash_table 中有没有 key 等于当前数值（cur_val）的情况，如果有则是找到了解，返回 hash_table 记录的下标以及当前下标。否则将 target - cur_val 以及当前下标的关系记录到 hash_table 中。

C++ 算法实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        const int size = nums.size();
        int tmp;

        for (int i = 0; i != size; ++i) {
            tmp = nums[i];
            if (m.find(tmp) != m.end()) {
                return {m[tmp], i};
            }

            m[target - tmp] = i;
        }

        return {-1, -1};
    }
};

更快的算法

在讨论区看到有耗时 8ms 的算法，比哈希方案快了一倍。基本思路是扫描一遍给出的数组，找出有可能符合条件的数字的最大和最小值，创建一个数组来记录数值与下标的对应关系，再扫描一遍给定的数组，找出合适的解。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // Since x1 + x2 = target, we can in one loop
        // mark both x1 and x2 in some additional array where we'll keep indices
        // Though to build that array we'd need another loop

        int min = nums[0], max = min;
        // first loop to find max and min integers
        for (int i = 0;i < nums.size();i++) {
            if (nums[i] < min) min = nums[i];
            if (nums[i] > max) max = nums[i];
        }

        // valid range for input integers relative to target
        int sMin;
        int sMax;
        if(min < target - max) {
            sMin = min;
        } else {
            sMin = target - max;
        }

        if(max > target - min) {
            sMax = max;
        } else {
            sMax = target - min;
        }

        // array to keep indices of valid input integers
        // initialize with -1
        int size = 1 + sMax - sMin;
        int arr[size];

        // for (int i = 0; i < arr.length;i++)
        //     arr[i] = -1;
        fill(arr,arr+size,-1);

        // second loop
        int offset = -sMin;

        for (int i = 0;i < nums.size();i++) {
            // Skip if integer is not from a valid range
            if (nums[i] > sMax || nums[i] < sMin) continue;

            // if found valid X1 and corresponding element of indices array is still -1
            // then mark its pair X2 = target - X1 in indices array
            if (arr[nums[i] + offset] == -1) {
                arr[target-nums[i] + offset] = i;
            } else {
                return {arr[nums[i] + offset],i};
            }
        }

        return {0,0};
    }
};

这种解法相对哈希表来说，主要利用了数组寻址快的特性。但需要注意的是在某些情况下（sMax 和 sMin 相差过大）会导致生成的临时数组过大，耗用大量内存，同时这种情况下也将耗费大量时间初始化这个数组。不过 LeetCode 给出的 testcase 明显没有测试这种情况。

2019年11月更新，由于 LeetCode 更新了 testcase ，这个算法已经不适用，如：[50000000,3,2,4,50000000]

凌云的博客

行胜于言