電面:1つの配列にkの2つの数を探し出す

タイトルの通り、実はLeetCodeにも道の差が少ない問題があり、Two Sumはこの2つの数の対応する下付き文字を返します.では、LeetCodeの問題に従って書きましょう.まず二重ポインタの方法を使いますが、LeetCodeの上に下付き文字を返すように要求されているので、sortで元の配列を直接ソートすることはできません.前の元の下付き文字に影響します.まず配列をコピーしなければなりません二重ポインタは何も言うことはありません.もう順番ができているので、一つは一番左端から、一つは一番右端から行きます.これを書くのは主にCのqsortソートを学ぶためです.
Two Sum Cコード:

typedef struct{
    int val;
    int idx;
}Node;
int cmp(const void* a,const void* b)
{
    return (*(Node*)a).val-(*(Node*)b).val;
}
int* twoSum(int *nums,int numsize,int target)
{
    int* res=(int*)malloc(sizeof(int)*2);
    if(numsize==0)
    {
        return res;
    }
    Node* nodes=(Node*)malloc(sizeof(Node)*numsize);
    for(int i=0;i<numsize;i++)
    {
        nodes[i].val=nums[i];
        nodes[i].idx=i;
    }
    qsort(nodes,numsize,sizeof(Node),cmp);
    int low=0,high=numsize-1;
    while(low<high)
    {
        if(nodes[low].val+nodes[high].val==target)
        {
            if (nodes[low].idx < nodes[high].idx)
            {
                res[0] = nodes[low].idx;
                res[1] = nodes[high].idx;
            }
            else
            {
                res[1] = nodes[low].idx;
                res[0] = nodes[high].idx;
            }
            break;
        }
        else if(nodes[low].val+nodes[high].val<target)
        {
            low++;
        }
        else
        {
            high--;
        }
    }
    return res;
}

16/16 test cases passed. Status: Accepted Runtime: 4 ms
下書きに戻るから、適当なのはハッシュでやるべきだ.問題を抽象化することができる.x+y=targetを知りたいなら、関数関係y=target-x、f:A->Bをこのように定義することができます.関数の定義ドメインAは、与えられた配列である.値ドメインは、Aのすべての要素の像の集合Cである.私たちが見つけたいy∈SはSは、値ドメイン集合Cと定義ドメイン集合Aとの交差である(y∈C^y∈Aは所与の配列の中で2つの数を探すため).遍歴するたびに関数関係y=target-xで1つのyを得ることができるが、私たちはy∈Sだけを探す.では、どのようにSを探すのか.大まかな考え方は、1つの空の集合Dに対して、y=target-xで得られたy∉Dに対して、私たちはxをDに追加し、Dの中ですべてxに相当し、y=target-xで得られたy∈D,ではyはSに属する.

vector<int> twoSum(vector<int>& nums, int target) {
        int len=nums.size();
        vector<int> res;
        if(len==0){
            return res;
        }
        unordered_map<int,int> m;
        int y;
        for(int i=0;i<len;i++){
            y=target-nums[i];
            if(m.find(y)==m.end()){//m    
                m[nums[i]]=i;
            }
            else{
                res.push_back(m[y]);
                res.push_back(i);
                break;
            }
        }
        return res;
    }

16/16 test cases passed. Status: Accepted Runtime: 16 ms