LeetCode OJ 1Two Sum
來源：程序員人生 發(fā)布時間：2015-06-19 09:16:50 閱讀次數(shù)：3687次
https://leetcode.com/problems/two-sum/
水題1發(fā)吧，不過退役以來很少做題了，真是退步太利害，沒斟酌全
題意:給1個數(shù)組，也1個target，問哪兩個數(shù)加起來可以得到target
答案：桶排orHash
1、注意，桶排序，而且桶的深度不1定是1，所以hash[i]表示i個數(shù)而不是是否是存在
2、由于觸及下標(biāo)，所以1定謹(jǐn)慎數(shù)組的數(shù)可以是分?jǐn)?shù)，我的做法是，找到min(x[i])，如果min(x[i])<0，那末target+=⑵*min(x[i]),x[i]+=（⑴）*min(x[i]),
非常不習(xí)慣的是，LeetCode OJ竟然沒有給定數(shù)的范圍，這個很頭疼，數(shù)組開多大呢。。。
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;
}
};
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
