「每日一道算法题」Two Sum

OJ address

OJ website : 1. Two Sum

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution in C

1. 暴力求解 36ms AC

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

int* twoSum(int* nums, int numsSize, int target) {
    int *a = malloc(2 * sizeof(int));
    a[0] = 0;
    a[1] = 0;
    for (int i = 0; i < numsSize; ++i) {
        for (int j=i+1;j<numsSize;++j) {
            if (target == (nums[i]+nums[j])) {
                a[0] = i;
                a[1] = j;
                return a;
            }
        }
    }
    return a;
}

int main(int argc, char const *argv[])
{
    int t[3]  = {3,2,3};
    int *a = twoSum(t, 3, 6);
    printf("a:%d,%d\n", a[0], a[1]);
    return 0;
}

2. 快排+查找 0ms AC

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

struct object {
    int value;
    int index;
};

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

int* twoSum(int* nums, int numsSize, int target) {
    int *a = malloc(2 * sizeof(int));
    a[0] = 0;
    a[1] = 0;

    struct object *objectArray = malloc(numsSize * sizeof(struct object));
    for (int i = 0; i < numsSize; ++i) {
        objectArray[i].value = nums[i];
        objectArray[i].index = i;
    }
    qsort(objectArray, numsSize, sizeof(struct object), compare);
    int i = 0;
    int n = numsSize-1;
    while (n > i) {
        int diff = target - objectArray[0].value;
        if (objectArray[n].value > diff) {
            --n;
            continue;
        }
        break;
    }
    int j = 0;
    j = n;
    while (i<j) {
        int diff = target - objectArray[i].value;
        if (diff < objectArray[j].value) {
            --j;
        }
        else if (diff > objectArray[j].value) {
            j=n;
            ++i;
        }
        else {
            a[0] = objectArray[i].index;
            a[1] = objectArray[j].index;
            return a;
        }
    }
    return NULL;
}

int main(int argc, char const *argv[])
{
    int t[3]  = {5,5};
    int *a = twoSum(t, 2, 10);
    printf("a:%d,%d\n", a[0], a[1]);
    return 0;
}

Solution in Python

#!/usr/bin/python3

class Solution(object):
    def twoSum(self, nums, target):
        myDict = {}
        for i in xrange(0,len(nums)):
            if target-nums[i] in myDict:
                return [myDict[target-nums[i]], i]
            myDict[nums[i]] = i

if __name__ == '__main__':
    a = Solution()
    dd = [5,5]

    c = a.twoSum(dd,10)
    print c

My Idea

给定一个整数数列，找出其中和为特定值的那两个数。你可以假设每个输入都只会有一种答案，同样的元素不能被重用。

1. 暴力求解：比较容易想到的方法是遍历数组中的所有数字，此种方法时间复杂度比较高O(n^2)
2. 定义一个字典的，便利数组nums，将元素当做key存入字典中，然后将数组的角标当做value存入字典中，遍历的数组的时候，也在寻找字典中是否包含另一个target-nums[i]，如果包含，则成功找到。这种算法的效率是O(n)
3. 用C语言，由于不带MAP的STL，通过声明结构体，所以通过快速排序，将元素排好序，去除大于元素中target-min的所有元素，因为这个元素不可能包含在结果中。去掉后，然后在进行查找，思路可见代码，这种效率是O(n)。0ms AC这道题。