Leetcode 1： Two Sum

问题描述

给定一个整数数组和一个目标数，返回两个下标，使数组中这两个下标所代表的数字之和等于目标数。
你可以认为每组输入有且仅有一个正解，除此之外，两个下标不应当相等。

例子：
给定一数组nums = [2, 7, 11, 15]，目标数target = 9
因为nums[0] + nums[1] = 2 + 7 = 9 = target，所以最后返回[0, 1]。

解题思路

显然的，本题最直接明了的方式就是暴力循环两个数组，依次算出所有和，并判定它是否与目标数相等，可以写出：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret { 0, 1 };
        for (int i = 0; i < nums.size(); i++) {
            ret[0] = i;
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    ret[1] = j;
                    return ret;
                }
            }
        }
    }
};

这里我们发现，已知nums[i]和target，nums[j]可以取的值是固定的，所以可以不必每次都做加法运算，将内循环改为：

            int tar = target - nums[i];
            ret[0] = i;
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[j] == tar) {
                    ret[1] = j;
                    return ret;
                }
            }

但这里只是改进了常数级别的时间复杂度，有没有什么方法只遍历数组一次就解决呢？如果想要只遍历一次就解决，主要的矛盾还是在如何不必循环就快速的查询出target - nums[i]是否在之前存在过。这里我使用了map作为查询的方法。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> exist;
        vector<int> ret { 0, 1 };
        for (int i = 0; i < nums.size(); i++) { 
            int comp = target - nums[i];
            if (exist[comp] != 0) {
                ret[0] = exist[comp] - 1;
                ret[1] = i;
                return ret;
            }
            exist[nums[i]] = i + 1;
        }
    }
};

果然，改进之后，时间复杂度大幅度降低。通过时间由166ms降低为9ms。