type
Post
status
Published
date
Feb 19, 2023
slug
summary
给定一个整数数组 nums  和一个整数目标值 target ,请你在该数组中找出 和为目标值 target   的那 两个  整数,并返回它们的数组下标。
tags
c++
leetcode
category
算法
icon
password

两数之和

题解

三种解法

1.暴力法

两层for循环,很简单不多赘述,时间复杂度

2.二分查找

先顺序遍历,枚举每个数,然后利用二分法在剩余的数中查看是否存在 时间复杂度:
代码
#include<iostream> #include<stdio.h> #include<vector> #include<cstring> #include<algorithm> using namespace std; int tar,n,tem; int main(){ vector<int>a; cin>>n>>tar; int t,c=0; for(int i=0;i<n;i++){ cin>>tem; a.push_back(tem); } int len=a.size(); vector<vector<int>> vec(len); for(int i=0;i<len;i++){ vec[i].push_back(a[i]); vec[i].push_back(c); c++; } sort(vec.begin(),vec.end()); int d[2],l,r; for(int i=0;i<len;i++){ //确定第一个数 t=vec[i][0]; d[0]=vec[i][1]; int m=tar-t; l=i; r=len-1; //二分查找,数组中组成target的另一个数,找符合条件的最右边的数 while(l<r){ int mid=l+(r-l+1)/2; if(m>=vec[mid][0]) l=mid; else r=mid-1; } if(m==vec[l][0]){ d[1]=vec[l][1]; break; } } if(d[0]<d[1]) printf("[%d,%d]\n",d[0],d[1]); else printf("[%d,%d]\n",d[1],d[0]); return 0; }

3.哈希表法

该算法的思想就是顺序遍历nums,然后再hashtable中去找,如果不存在,就把当前 加入hashtable,最终的效果是总能在hashtable中找到组成target的另一个整数。
该方法用 map 实现,map 是 STL 的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在 map 中出现一次,第二个可能称为该关键字的值)的数据处理能力
代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int,int> hashtable; int len=nums.size(); // 定义一个map的迭代器,能记录遍历到map的数据位置 map<int,int>::iterator it; for(int i=0;i<len;i++){ it = hashtable.find(target-nums[i]); // 如果能在hashtable找到数据,it就能获取到数据位置,如果没有,it就是end的位置 if(it!=hashtable.end()){ return {it->second,i}; } hashtable[nums[i]]=i; } return {}; } };
 

4.

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(), l = 0, r = n - 1; vector<pair<int, int>> arr(n); for(int i=0;i<n;i++) arr[i] = {nums[i], i}; sort(arr.begin(), arr.end()); while(l<r){ if(arr[l].first + arr[r].first < target) l++; else if(arr[l].first + arr[r].first > target) r--; else return {arr[l].second, arr[r].second}; } return {}; } };
两数相加Github