数据结构与算法之两数之和

原创
05/09 20:27
阅读数 14

一、说明

 
        给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
 
        你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
 
        示例:
                给定 nums = [2, 7, 11, 15] , target = 9 。
                因为 nums[0] + nums[1] = 2 + 7 = 9 ,
                所以返回 [0, 1]
 

二、解决方案参考

        1. Swift 语言

 

         2. JavaScript 语言

 

         3. Python 语言

        4. Java 语言
        
        5. C++ 语言
        6. C 语言

#include <stdio.h>
#include <stdlib.h>

struct object {
    int val;
    int index;
};

static int compare(const void *a, const void *b)
{
    return ((struct object *) a)->val - ((struct object *) b)->val;
}

static int * twosum(int *nums, int numsSize, int target)
{
    int i, j;
    struct object *objs = malloc(numsSize * sizeof(*objs));
    for (i = 0; i < numsSize; i++) {
        objs[i].val = nums[i];
        objs[i].index = i;
    }
    qsort(objs, numsSize, sizeof(*objs), compare);
    
    int count = 0;
    int *results = malloc(2 * sizeof(int));
    i = 0;
    j = numsSize - 1;
    while (i < j) {
        int diff = target - objs[i].val;
        if (diff > objs[j].val) {
            while (++i < j && objs[i].val == objs[i - 1].val) {}
        } else if (diff < objs[j].val) {
            while (--j > i && objs[j].val == objs[j + 1].val) {}
        } else {
            results[0] = objs[i].index;
            results[1] = objs[j].index;
            return results;
        }
    }
    return NULL;
}

int main(void)
{
    //int nums[] = {-1, -2, -3, -4, -5};
    //int target = -8;
    //int nums[] = {0,4,3,0};
    //int target = 0;
    int nums[] = { 3, 2, 3 };
    int count = sizeof(nums) / sizeof(*nums);
    int target = 6;
    int *indexes = twosum(nums, count, target);
    if (indexes != NULL) {
        printf("%d %d
", indexes[0], indexes[1]);
    } else {
        printf("Not found
");
    }

    return 0;
}

 

--------------------------------------

版权声明:本文为【PythonJsGo】博主的原创文章,转载请附上原文出处链接及本声明。

博主主页:https://my.oschina.net/u/3375733

本篇文章同步在个人公众号:

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部