顿搜
飞过闲红千叶，夕岸在哪
类目归类
LeetCode 0001 Two Sum [解题报告][数组处理]
04/14
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].
Code
[code lang=c]
#include<stdio.h>
void QSort(int* nums, int* index, int head, int tail)
{
if (head >= tail)
{
return;
}
int left = head, right = tail, numTmp = nums[left], indexTmp = index[left];
while (left < right)
{
while (left < right && nums[right] >= numTmp) right--;
if (left < right)
{
nums[left] = nums[right];
index[left] = index[right];
left++;
}
while (left < right && nums[left] < numTmp) left++;
if (left < right) {
nums[right] = nums[left];
index[right] = index[left];
right--;
}
}
nums[left] = numTmp; index[left] = indexTmp;
QSort(nums, index, head, left - 1);
QSort(nums, index, left + 1, tail);
}
int* twoSum(int* nums, int numsSize, int target)
{
if (numsSize < 2) {
return NULL;
}
int* index = (int*)malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize; i++) {
index[i] = i;
}
QSort(nums, index, 0, numsSize - 1);
int left = 0, right = numsSize - 1;
if (left == right) {
return NULL;
}
int num = nums[left] + nums[right];
while (num != target)
{
if (num > target && --right > left) {}
else if (num < target && ++left < right) {}
if (left == right)
{
return NULL;
}
num = nums[left] + nums[right];
}
if (num == target) {
int* result = malloc(2 * sizeof(int));
result[0] = index[left];
result[1] = index[right];
return result;
}
return NULL;
}
int main()
{
int nums[4] = { -3,4,3,90 };
int* result = twoSum(nums, 4, 0);
printf("[%d,%d]", result[0], result[1]);
getchar();
return 1;
}
[/code]
Submission Details
