$\textrm{Problem Description : }$$\href{https://leetcode.cn/problems/two-sum/}{\textrm{LeetCode1-两数之和}}$

搜索是否存在两个数之和等于目标值，返回这两个数的下标，保证答案唯一

$\textrm{Solution:}$

  1. 排序后，枚举每个nums[i]，二分查找target-nums[i]
  2. 排序后，双指针查找
  3. 哈希表查找

因为要返回下标，所以排序的处理要繁琐一些，给出方法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}$