LeetCode OJ 1Two Sum
来源：程序员人生 发布时间：2015-06-19 09:16:50 阅读次数：3548次
https://leetcode.com/problems/two-sum/
水题1发吧，不过退役以来很少做题了，真是退步太利害，没斟酌全
题意:给1个数组，也1个target，问哪两个数加起来可以得到target
答案：桶排orHash
1、注意，桶排序，而且桶的深度不1定是1，所以hash[i]表示i个数而不是是否是存在
2、由于触及下标，所以1定谨慎数组的数可以是分数，我的做法是，找到min(x[i])，如果min(x[i])<0，那末target+=⑵*min(x[i]),x[i]+=（⑴）*min(x[i]),
非常不习惯的是，LeetCode OJ竟然没有给定数的范围，这个很头疼，数组开多大呢。。。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int tmp,cnt=0;
int num[100001],id[100001];
int t = 0;
memset(num,0,sizeof(num));
memset(id,0,sizeof(id));
for(int i=0;i<nums.size();i++){
tmp = nums[i];
t = min(t,tmp);
}
cnt=0;
if(t<0){
t=-t;
for(int i=0;i<nums.size();i++){
nums[i] += t;
int tmp= nums[i];
num[tmp] ++;
cnt++;
id[tmp]=cnt;
//cout << nums[i] << endl;
}
target += 2*t;
}else{
for(int i=0;i<nums.size();i++){
int tmp= nums[i];
num[tmp] ++;
cnt++;
id[tmp]=cnt;
//cout << nums[i] << endl;
}
}
//cout << "ttt=" << target << " " << t << endl;
int flag=0;
vector<int>ans;
for(int i=0;i<cnt;i++){
if( nums[i]<=target ){
if(num[target-nums[i]] ){
if(target-nums[i] == nums[i] && num[nums[i]]<2)continue;
flag =1;
ans.push_back(i+1);
ans.push_back( id[ target-nums[i] ] );
//ans = i+id[ target-nums[i] ];
break;
}
}
}
return ans;
}
};
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
