twoSum
2024-10-19 04:31:59
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
第一次的代码,思路很简单:
#include <iostream>
#include <algorithm>
#include <vector> using namespace std; class Solution{
public:
vector<int> twoSum(vector<int>& nums, int target){
int i = 0;
int j = 0;
vector<int> result; for(i=0; i<nums.size()-1; i++){
for(j=i+1; j<nums.size(); j++){
if(nums[i] + nums[j] == target){
result.push_back(i+1);
result.push_back(j+1);
}
}
}
return result;
}
}; int main(){
vector<int> src;
int input;
int target;
int i =0; vector<int> result; do{
cin>>input;
src.push_back(input);
if(cin.get() == '\n'){
break;
}
}while(1); cin>>target; Solution s;
result = s.twoSum(src, target); for(i=0; i<result.size(); i++){
cout<<result[i]<<endl;
} return 0;
}
最后发现,由于复杂度是O(n^2)系统无法接受,需要降低算法复杂度。。。
现在看到别人用map来解决这个问题
#include <iostream>
#include <algorithm>
#include <vector>
#include <map> using namespace std; class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> result;
map<int, int> m;
if (numbers.size() < 2)
return result;
for (int i = 0; i < numbers.size(); i++)
m[numbers[i]] = i; map<int, int>::iterator it;
for (int i = 0; i < numbers.size(); i++) {
if ((it = m.find(target - numbers[i])) != m.end())
{
if (i == it->second) continue;
result.push_back(i+1);
result.push_back(it->second+1);
return result;
}
}
return result;
}
}; int main(){
vector<int> src;
int input;
int target;
int i =0; vector<int> result; do{
cin>>input;
src.push_back(input);
if(cin.get() == '\n'){
break;
}
}while(1); cin>>target; Solution s;
result = s.twoSum(src, target); for(i=0; i<result.size(); i++){
cout<<result[i]<<endl;
} return 0;
}
最新文章
- [Data Structure] Bit-map空间压缩和快速排序去重
- Memcache 内存分配策略和性能(使用)状态检查
- 后台运行程序screen or nohup
- HBase 分布式环境搭建
- java端口扫描(原创)
- 千人基因组计划数据库下载某段区域SNP
- Leetcode-203 Remove Linked List Elements
- Java笔记--Java的List、Iterator用法
- 2nd_SE-结对编程1-基于flask框架的四则运算生成器
- RobotFramework下的http接口自动化Set Request Body 关键字的使用
- 新概念英语(1-107)It&#39;s Too Small.
- JAVA RPC (六) 之手把手从零教你写一个生产级RPC之client的代理
- MAC终端神器iterm2——告别黑白
- Linux(Centos)下调整分区大小(以home和根分区为例)
- 阿里架构师的工作总结:Spring Cloud在架构演进中起到的作用
- Jmeter NonGUI模式
- awk 相关的复习
- JavaScript -- URL编码
- 【BZOJ1862】[ZJOI2006]游戏排名系统 (Splay)
- Fragment 的生命周期及使用方法详解