题解 | #两数之和#

两数之和

http://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f

题意理解

找出数组中和等于目标值的两个数,输出它们的下标,注意先输出小的下标。输出结果存在且唯一。

方法一

题目要求两个数值对应的index,首先想到双指针的方法。

先对数组进行排序,注意在排序时,原先的index也要跟着数值一起交换位置,否则最后输出新的index是错误的。这就需要我们自己定义一个结构体,里面存放数值和对应的旧index。

两个指针(非数据结构的指针)i,j分别指向开头和结尾,如果number[i]+number[j]==target即得到答案。若和小于target,说明加数小了,i就右移;若和大于target,说明加数大了,j左移。每一个数只要扫一遍就可以了。
示意图如下:
图片说明

证明算法不会错过解:
当i扫到number[i']的时候,不可能和j右侧的数值相加等于target。因为之前j位于j'(j'>j)的时候,指针i右移直到两数之和大于target时停止,此时i<i',所以number[i']+number[j']一定大于target。

具体代码如下:

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    //定义结构体Num_index,把数值和原先的index都对应地存储起来
    typedef struct {
        int number;
        int index;
    }Num_index;

    //需要自己写sort函数里面的比较方法,这里比较number的数值
    static bool compare(Num_index a, Num_index b) {
        return (a.number < b.number);
    }

    vector<int> twoSum(vector<int>& numbers, int target) {
        //定义一个Num_index类型的数组,将数值及其原先的index存入
        vector<Num_index> num_index;
        for (int i=0;i<numbers.size();i++) {
            Num_index x;
            x.number = numbers[i];
            x.index = i;
            num_index.push_back(x);
        }
        sort(num_index.begin(), num_index.end(), compare);
        vector<int> ans;

        //排序后,从两端向中间搜索;当i>=j时搜索完毕。
        int i=0,j=numbers.size()-1;
        while (i<j) {
            if (num_index[i].number+num_index[j].number == target) {
                //注意先输出原先index小的值
                ans.push_back(min(num_index[i].index,num_index[j].index)+1);
                ans.push_back(max(num_index[i].index,num_index[j].index)+1);
                return (ans);
                break;
            }
            else if (num_index[i].number+num_index[j].number < target) {
                i++;
            }
            else j--;
        }
        return ans;
    }
};

时间复杂度:快速。使用快速排序的时间为;双指针遍历时,每个数值只经过了一遍,为
空间复杂度:。创建了一个结构体数组重新存储数值和对应的旧index。

方法二

当我们遍历到某个numbers[i]时,就要看target-numbers[i]是否在数组中。这本来是一个双重循环,需要O(n^2)的时间。

考虑使用哈希表来标记某个数是否存在于数组中,把双重循环改为并行的两次循环。先遍历一遍来建立哈希表mymap,哈希规则为mymap[numbers[i]] = i;再遍历一遍数组number,查看target-numbers[i]是否在哈希表中,注意两个加数不能重复。

哈希表示意图如下:
图片说明

具体代码如下:

class Solution {
public:
    /**
     * 
     * @param numbers int整型vector 
     * @param target int整型 
     * @return int整型vector
     */
    vector<int> twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> mymap;
        //建立哈希表
        for (int i=0;i<numbers.size();i++) {
            mymap[numbers[i]] = i;
        }
        vector<int> ans;

        for (int i=0;i<numbers.size();i++) {
            int d = target - numbers[i];
            //先判断target与numbers[i]的差是否在hash中,其次还要判断是否重复了。
            if (mymap.count(d)!=0 && mymap.at(d)!=i) {
                ans = {i+1, mymap.at(d)+1};
                break;
            }
        }
        return ans;
    }
};

时间复杂度:。建立哈希表和使用哈希表进行查找的时间都为
空间复杂度:。建立一个哈希表需要的空间。

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务