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; }
本文标题:[leetcode题解]001.Two Sum
本文链接地址:https://www.iaccepted.net/algorithm/leetcode/172.html