给定整数的一个数组,找出这样的两个数,它们的加和等于一个特定的目标数字(target)。
twoSum
函数应该返回两个数的索引,这两个数相加等于目标数字,其中indexl
必须小于index2
。请注意,返回的结果(index1
和index2
)不是基于0的。
可以假设对每一个输入来说,都只有一个解决方案。
输入:numbers={2,7,11,15}, target=9
输出:index1=1,index2=2
最直观明了的解法是通过暴力搜索,使用两个嵌套的循环来遍历所有可能,时间复杂度为 O ( n ∗ n ) O(n*n) O(n∗n)。但是很明显,这不是出题者想看到的结果。
从左往右扫描一遍,然后将整数及其索引存到map
中。然后再扫描一遍,对每一个整数
K
K
K,搜索
t
a
r
g
e
t
−
K
target-K
target−K在map
中是否存在即可。如果存在,则输出
K
K
K及
t
a
r
g
e
t
−
K
target-K
target−K的下标。时间复杂度为
O
(
n
)
O(n)
O(n)。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int maxn=1e6+5; vector<int> twosum(vector<int> &numbers,int target){ map<int, int> mapping; vector<int> result; for (int i = 0; i < numbers.size();i++){ mapping[numbers[i]] = i; } for (int i = 0; i < numbers.size();i++){ int searched = target - numbers[i]; if(mapping.find(searched)!=mapping.end()&&i!=mapping[searched]){ result.push_back(i + 1); result.push_back(mapping[searched] + 1); break; } } return result; } int main(){ vector<int> numbers = {2, 7, 11, 15}; int target = 9; vector<int> result = twosum(numbers, target); for (int i = 0; i < result.size();i++){ cout << "index" << i << ": " << result[i] << endl; } return 0; }
首先将数组排序,然后双指针从首尾往中间扫描。时间复杂度为
O
(
n
∗
l
g
n
)
O(n*lgn)
O(n∗lgn)。因
为要求返回原数组的下标,所以在排序的时候还要有额外的数组来存储下标信息。
双指针扫描
双指针问题是对于普通问题的一种特殊解法,往往要求问题是线性的,可以用双指针来遍历,从许多解中找到一个最大或者最小的解。双指针一般可以分别放在首尾处,用来往中间靠拢,或者者放在头部,用来划分区间。
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int maxn=1e6+5; struct Node{ int val; int index; Node(int pVal,int pIndex):val(pVal),index(pIndex){} }; static bool compare(const Node &left,const Node &right){ return left.val < right.val; } vector<int> twosum(vector<int> &numbers,int target){ vector<Node> elements; for (int i = 0; i < numbers.size();i++){ elements.push_back(Node(numbers[i], i)); } std::sort(elements.begin(), elements.end(), compare); int start = 0, end = numbers.size() - 1; vector<int> result; while(start<end){ int sum = elements[start].val + elements[end].val; if(sum == target){ result.push_back(elements[start].index + 1); if(elements[start].index<elements[end].index) result.push_back(elements[end].index + 1); else result.insert(result.begin(), elements[end].index + 1); break; }else if(sum>target) end--; else start++; } return result; } int main(){ vector<int> numbers = {2, 7, 11, 15}; int target = 9; vector<int> result = twosum(numbers, target); for (int i = 0; i < result.size();i++){ cout << "index" << i << ": " << result[i] << endl; } return 0; }