[leetcode题解]001.Two Sum

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].

给定一个数组和一个目标值,求在这个数组中的两个数之和等于目标值,而且题目中已经明确说明,有且只有一组解存在,题目要求不是找出这一对数字,而是要找到他们在数组中的下标。

这个题目解法就是双指针法,但要求先排序,排序的话下标就会变掉,所以简单的思路就是建立一个结构体数组,结构体中记录数字以及他在原数组中的下标,然后按数字对整个结构体数

组进行排序,再使用双指针法即可,得到目标值下两个数的下标返回即可。

struct element {
    int num;
    int loc;
};

int cmp(void *a, void *b) {
    struct element *pa = (struct element *)a;
    struct element *pb = (struct element *)b;
    
    return pa->num - pb->num;
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int i = 0;
    struct element *eles = malloc(sizeof(struct element) * numsSize);
    int *res = malloc(2 * sizeof(int));
    int idx = 0;
    int li = 0, ri = numsSize - 1;
    
    for (i = 0; i < numsSize; i++) {
        eles[i].num = nums[i];
        eles[i].loc = i;
    }
    qsort(eles, numsSize, sizeof(struct element), cmp);
    while (li < ri) {
        int sum = eles[li].num + eles[ri].num;
        if (sum < target)
            li++;
        else if (sum > target)
            ri--;
        else {
            res[0] = eles[li].loc;
            res[1] = eles[ri].loc;
            break;
        }
    }
    return res;
}

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]001.Two Sum

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/172.html

相关文章