凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 1. Two Sum

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


题目

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.

思路

给定一个数组,以及 target,在数组中找出两个数值相加等于 target 的下标,输入数据有且只有一种解。 首先想到就是通过哈希表(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 明显没有测试这种情况。