美文网首页
0001-两数之和

0001-两数之和

作者: liyoucheng2014 | 来源:发表于2019-01-20 20:40 被阅读0次

两数之和

方案一


原数组排序,我们用两个指针分别指向数组首尾两个数,如果两个数和正好为target,则将这两个数一起存入结果中。然后就是跳过重复数字的步骤了,两个指针都需要检测重复数字。如果两数之和小于target,则我们将左边那个指针i右移一位,使得指向的数字增大一些。同理,如果两数之和大于target,则我们将右边那个指针j左移一位,使得指向的数字减小一些。

C-源代码


#include <stdlib.h>
#include <string.h>

struct object {
    int key;
    int value;
};

int compareObject(const void *a, const void *b) {
    return ((struct object*)a)->value - ((struct object*)b)->value;
}

int* twoSum(int* nums, int numsSize, int target) {
    struct object *objs = (struct object*)malloc(sizeof(*objs) * numsSize);
    for(int i = 0; i < numsSize; i++) {
        objs[i].key = i;
        objs[i].value = nums[i];
    }
    
    qsort(objs, numsSize, sizeof(*objs), compareObject);
    
    int left = 0;
    int right = numsSize - 1;
    while (left < right) {
        int diff = target - objs[left].value;
        if (diff < objs[right].value) {
            while (--right > left && objs[right].value == objs[right + 1].value) {
                
            }
        }
        else if (diff > objs[right].value) {
            while (++left < right && objs[left].value == objs[left - 1].value) {
                
            }
        }
        else {
            int *ret = (int *)malloc(sizeof(int) * 2);
            ret[0] = objs[left].key;
            ret[1] = objs[right].key;
            return ret;
        }
    }
    
    return NULL;
}

void test_0001() {
    int nums[5] = { 2, 7, 11, 15 };
    int target = 9;
    int *ret = twoSum(nums, sizeof(nums) / sizeof(nums[0]), target);
    printf("%d->%d\n",ret[0],ret[1]);
}

C++实现

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        unordered_map<int, int> m;
        vector<int> res;
        
        for (int i = 0; i < nums.size(); ++i) {
            
            m[nums[i]] = i;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            
            int t = target - nums[i];
            if (m.count(t) && m[t] != i) {
                
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        
        return res;
    }
};

参考Grandyang

相关文章

  • 0001-两数之和

    两数之和 方案一 原数组排序,我们用两个指针分别指向数组首尾两个数,如果两个数和正好为target,则将这两个数一...

  • 两数之和(golang)

    原题:两数之和 关联:两数之和 II - 输入有序数组(golang)两数之和 IV - 输入 BST(golang)

  • 两数之和 II - 输入有序数组(golang)

    原题:两数之和 II - 输入有序数组 关联:两数之和(golang)两数之和 IV - 输入 BST(golan...

  • 浅入浅出实现一个异步求和函数

    简化:两数之和 我们先来简单的实现一个异步两数之和函数 加深:多数之和 上面我们实现了两数之和,然后扩展到多数之和...

  • 两数之和,三数之和

    转载:https://www.cnblogs.com/DarrenChan/p/8871495.html 1. 两...

  • 两数之和&三数之和&四数之和&K数之和

    今天看了一道谷歌K数之和的算法题,忽然想起来之前在力扣上做过2、3、4数之和的题,觉得很有必要来整理一下。其实2、...

  • algrithrom

    求和问题,双指针解决 done 两数之和 三数之和 最接近三数之和 四数之和 链表反转问题 done 链表反转 链...

  • 「算法」两数之和 & 两数之和 II

    00001 两数之和 题目描述 给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只...

  • 两数之和

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案,且同样的元素不能被...

  • 两数之和

    两数之和 题目描述 Given an array of integers, return indices of t...

网友评论

      本文标题:0001-两数之和

      本文链接:https://www.haomeiwen.com/subject/wsjfjqtx.html