LeetCode OJ 1Two Sum
來源：程序員人生 發布時間：2015-06-19 09:16:50 閱讀次數：3683次
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;
}
};
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
