企业官网建设流程全解析

原题链接
这里提供两种题解，O（logn）的排序双指针法与O（n）的哈希表方法。
题目数据范围只有10⁴，所以暴力遍历O(n²)其实也没问题。

1.排序双指针

思路

• 结果是两个数，确定其中一个就可以知道结果。
• 排序后就可以使用双指针遍历求出结果。
  大致确定思路后就是具体实现。
• 排序需要保存下标与数据，所以需要一个结构体保存。
• 指针初始化在左右两侧，每一轮循环单独判断。小了就把左指针右移，大了就右移右指针

代码

classSolution{public:structnode{intnum;intindex;};vector<int>twoSum(vector<int>&nums,inttarget){intlen=nums.size();vector<node>data(len);for(inti=0;i<len;i++){data[i].num=nums[i];data[i].index=i;}sort(data.begin(),data.end(),[](node&a,node&b){returna.num<b.num;});intl=0,r=len-1;while(l<r){intsum=data[l].num+data[r].num;if(sum==target){return{data[l].index,data[r].index};}if(sum>target){r--;}elseif(sum<target){l++;}}return{};}};

2.哈希表

思路

• 哈希表查找平均 O（1），直接查找能否合并为target就可以得出答案。
• 注意数据种出现相同的数据，直接存储后判断会需要额外判断
• 所以遍历数据前判断能否拼凑成功，可以就直接返回结果，不行再存储

代码

classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){intn=nums.size();unordered_map<int,int>mp;for(inti=0;i<n;i++){autoit=mp.find(target-nums[i]);if(it!=mp.end()){return{i,it->second};}mp[nums[i]]=i;}return{};}};

本题数据量很小，所以还有多种方法。不过使用STL库中的哈希表相对很方便简洁，但是也需要额外注意边界情况。