$\textrm{Problem Description : }$$\href{https://leetcode.cn/problems/two-sum/}{\textrm{LeetCode1-两数之和}}$
搜索是否存在两个数之和等于目标值,返回这两个数的下标,保证答案唯一
$\textrm{Solution:}$
- 排序后,枚举每个nums[i],二分查找target-nums[i]
- 排序后,双指针查找
- 哈希表查找
因为要返回下标,所以排序的处理要繁琐一些,给出方法2的实现:
struct node { int val; int idx; node(){val = idx = 0;} node(int _val, int _idx) { val = _val; idx = _idx; } }; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); node *a = new node [n]; for(int i = 0;i < n;i++) { a[i].idx = i; a[i].val = nums[i]; } sort(a,a+n,[](const node &u,const node &v){ return (u.val == v.val)?(u.idx < v.idx):(u.val < v.val); }); int i = 0,j = nums.size()-1; while(1) { if(a[i].val+a[j].val == target) return {a[i].idx,a[j].idx}; else if(a[i].val+a[j].val > target)j--; else i++; } return {-1}; } };
$\textrm{Author}$@$\href{http://kuroko.info}{\textrm{Kuroko}}$
$\textrm{GitHub}$@$\href{https://github.com/SuperKuroko}{\textrm{SuperKuroko}}$
$\textrm{LeetCode}$@$\href{https://leetcode-cn.com/u/kuroko177/}{\textrm{kuroko177}}$
$\textrm{Last Modified: 2023-02-17 08:55}$
退出登录?