Leetcode1-两数之和

问题描述

解法

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

因为要返回下标，所以排序的处理要繁琐一些，给出方法2的实现:

cpp code

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};
    }
};

Author@Kuroko

GitHub@SuperKuroko

LeetCode@kuroko177

Last Modified: 2023-02-17 08:55