两数之和 56,608暴力查找排序加双指针

看到了就一块做了,两个题的要求差不多,条件不同: 给一个整数数组,找到两个数使得他们的和等于一个给定的数 target。 你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 1 到 n,不是以 0 开头。 样例 给出 numbers = [2, 7, 11, 15], target = 9, 返回 [1, 2].

两个数的条件不同,56给出的数组是乱序的,608给的数组是顺序的。

暴力查找

对于每一个数,在数组中查找和其和为目标数的数,注意两个数的索引不能相同,这样的时间复杂度是O(n^2),谁都能想到,不推荐。

排序加双指针

608

这个思路就比较好了,对于608给出的数据,直接排序加双指针就ok了,记得最后给索引加1。

 vector<int> twoSum(vector<int> &nums, int target) {
        auto beg=nums.begin();
        auto end=nums.end()-1;
        vector<int> res;
        int s=0;
        //两头
        while(beg<end)
        {
            if(*beg+*end==target)   //等于的话就刚刚好
            {res.push_back(beg-nums.begin()+1);
             res.push_back(end-nums.begin()+1);
             return res;
            }
            if(*beg+*end<target)    //小于的话就增加第一个
            {
             beg++;
            
            }
            else            //大于的话就减小后一个
            {
            end--;
            }
            
        }
                // write your code here
    }

56

这个倒是可以排序,但是记得要同时把索引也保存起来,因为最后要求返回的是索引,可以把值和索引做成一个pair放入vector里面,然后根据值来排序,这里的排序规则要自己写,sort函数的第三个参数是支持的,然后再双指针就可以了。

static bool MyComp(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}

vector<int> twoSum(vector<int> &numbers, int target) {

    vector<int> res;
    vector<pair<int, int>> nums;
    for (size_t i = 0; i<numbers.size(); i++)
    {
        nums.push_back(make_pair(numbers[i], i));     //把key和value分别存入map
    }
    sort(nums.begin(), nums.end(),MyComp);  //自定义排序规则
    auto beg = nums.begin();
    auto end = nums.end() - 1;
    while (beg != nums.end())
    {
        if(beg->first+end->first==target)
        {
            res.push_back(beg->second + 1);
            res.push_back(end->second + 1);
            break;
        }
        else if (beg->first + end->first < target)
            beg++;
        else if (beg->first + end->first > target)
            end--;
    }
    sort(res.begin(),res.end());
    return res; 
    // write your code here
}

既然用pair来做可以,那么干脆用map来做就行了,因为map是按照key进行自动排序的,不用自己排序,要注意需要用multimap来做,不要去重,用insert添加进去。 但是map就不能用双指针了,map的迭代器不支持减操作,但是map自己的find函数还是可以用的,按照key查找,返回对应的迭代器,如果不存在则返回尾后。 这样说起来vector也是可以用find的,但是为了体会这个过程,还是不用了的好。程序如下:注意map查找时,可能返回当前遍历的元素,要排除掉。

   vector<int> twoSum(vector<int> &numbers, int target) {

    vector<int> res;
    multimap<int,int> nums;
    for (size_t i = 0; i<numbers.size(); i++)
    {
        nums.insert(make_pair(numbers[i],i));     //把key和value分别存入map
    }
    auto beg = nums.begin();
    while (beg != nums.end())
    {
        
        auto f = nums.find(target-beg->first);  
        
        if (f != nums.end()&&f!=beg)   //不能等于自己,要不两个索引是一样的了。
        {
            res.push_back(beg->second + 1);
            res.push_back(f->second + 1);
            break;
        }
        beg++;
    }
    sort(res.begin(), res.end());
    return res; 
    // write your code here
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏从流域到海域

《Java程序设计基础》 第8章手记Part 2

第八章内容 Part 2 - … - 抽象类和抽象方法 - 接口及接口的实现 - 利用接口实现类的多重继承 - 内部库和匿名类 ...

2179
来自专栏闻道于事

Java常见问题

自古深情留不住,总是套路得人心 最近经历了一次惨无人道的程序员笔试,真的是“笔”试,默默地来整理一下…… 以后遇到问题要多整理…… 常见套路: 当一个变量被赋值...

4396
来自专栏lgp20151222

Java函数的传参机制

最近的一个项目,里面各种返回void,参数用引用类型,那叫一个熟和多,但是也把我绕糊涂了。

1772
来自专栏blackheart的专栏

[C#2] 1-泛型

1. 泛型概述 泛型是一种类型的多态;比如当我们写一个栈或者队列的时候,需要指定其数据类型,int一份代码,string一份代码,object的一份代码, 这些...

22810
来自专栏CodingToDie

Python学习(二):基础

第2 章 基础 Table of Contents 输入和输出 输出 输入 数据类型 整数 浮点数 字符串 布尔值 空值 变量 常量 输入和输出 输出 prin...

3375
来自专栏有趣的Python

5-C++远征之离港篇-学习笔记

2-2-2-C++Two-ReferenceStructDemo/main.cpp

1233
来自专栏Java爬坑系列

C\C++中声明与定义的区别

  声明和定义是完全同的概念,声明是告诉编译器“这个函数或者变量可以在哪找到,它的模样像什么”。而定义则是告诉编译器,“在这里建立变量或函数”,并且为它们分配内...

19110
来自专栏向治洪

Kotlin基础之委托

委托模式是软件设计模式中的一项基本技巧。在委托模式中,有两个对象参与处理同一个请求,接受请求的对象将请求委托给另一个对象来处理。 类委托 委托模式是替换继承的较...

1906
来自专栏Kevin-ZhangCG

[ Java面试题 ]基础篇之一

2165
来自专栏码云1024

JAVA 第二天 关键字

2917

扫码关注云+社区

领取腾讯云代金券