【leetCode】001Two Sum

2019-11-11 05:16:09

字體：大中小

來源：轉載

供稿：網友

【鏈接】：Two Sum

【描述】：Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example: Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. Subscribe to see which companies asked this question. 【思路】： C代碼：

int main(){ int n,arr[maxn]; int target; int ri,rj; memset(arr,0,sizeof(arr)); scanf("%d",&n); for(int i=0; i<n; ++i) scanf("%d",&arr[i]); scanf("%d",&target); for(int i=0; i<n; ++i){ for(int j=i+1; j<n; ++j){ if(arr[j]==(target-arr[i])) ri=i; rj=j; break; } break; } C++代碼：

class Solution{public: vector <int> twoSum(vector<int>&nums,int target) { unordered_map<int,int> map; for(int i=0; i<nums.size(); ++i){ auto tp=map.find(target-nums[i]); if(tp!=map.end()) { return {tp->second,i}; } map[nums[i]]=i; } }};

　unordered_map和map類似，都是存儲的key-value的值，可以通過key快速索引到value。不同的是unordered_map不會根據key的大小進行排序，

存儲時是根據key的hash值判斷元素是否相同，即unordered_map內部元素是無序的，而map中的元素是按照二叉搜索樹存儲，進行中序遍歷會得到有序遍歷。