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

2. Example

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

3. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="C (S=O(N))" active="active"]

void QuickSort(int* aNums, int* aIndex, int aHead, int aTail)
{
	if (aHead >= aTail)
	{
		return;
	}
	int mLeft = aHead, mRight = aTail, mNumTmp = aNums[mLeft], mIndexTmp = aIndex[mLeft];

	while (mLeft < mRight)
	{
		while (mLeft < mRight && aNums[mRight] >= mNumTmp) mRight--;
		if (mLeft < mRight)
		{
			aNums[mLeft] = aNums[mRight];
			aIndex[mLeft] = aIndex[mRight];
			mLeft++;
		}
		while (mLeft < mRight && aNums[mLeft] < mNumTmp) mLeft++;
		if (mLeft < mRight) {
			aNums[mRight] = aNums[mLeft];
			aIndex[mRight] = aIndex[mLeft];
			mRight--;
		}
	}
	aNums[mLeft] = mNumTmp; aIndex[mLeft] = mIndexTmp;

	QuickSort(aNums, aIndex, aHead, mLeft - 1);
	QuickSort(aNums, aIndex, mLeft + 1, aTail);
}

int* twoSum(int* nums, int numsSize, int target) 
{
	if (numsSize < 2) {
		return NULL;
	}

	int* mIndex = (int*)malloc(numsSize * sizeof(int));

	for (int i = 0; i < numsSize; i++) {
		mIndex[i] = i;
	}

	QuickSort(nums, mIndex, 0, numsSize - 1);

	int mLeft = 0, mRight = numsSize - 1;

	if (mLeft == mRight) {
		return NULL;
	}

	int mNum = nums[mLeft] + nums[mRight];

	while (mNum != target)
	{
		if (mNum > target && --mRight > mLeft) {}
		else if (mNum < target && ++mLeft < mRight) {}
		if (mLeft == mRight)
		{
			return NULL;
		}
		mNum = nums[mLeft] + nums[mRight];
	}

	if (mNum == target) {
		int* mResult = malloc(2 * sizeof(int));
		mResult[0] = mIndex[mLeft];
		mResult[1] = mIndex[mRight];
		return mResult;
	}
	return NULL;
}

[/restab]
[restab title="C (TEST)"]

#include

void QuickSort(int* aNums, int* aIndex, int aHead, int aTail)
{
	if (aHead >= aTail)
	{
		return;
	}
	int mLeft = aHead, mRight = aTail, mNumTmp = aNums[mLeft], mIndexTmp = aIndex[mLeft];

	while (mLeft < mRight)
	{
		while (mLeft < mRight && aNums[mRight] >= mNumTmp) mRight--;
		if (mLeft < mRight)
		{
			aNums[mLeft] = aNums[mRight];
			aIndex[mLeft] = aIndex[mRight];
			mLeft++;
		}
		while (mLeft < mRight && aNums[mLeft] < mNumTmp) mLeft++;
		if (mLeft < mRight) {
			aNums[mRight] = aNums[mLeft];
			aIndex[mRight] = aIndex[mLeft];
			mRight--;
		}
	}
	aNums[mLeft] = mNumTmp; aIndex[mLeft] = mIndexTmp;

	QuickSort(aNums, aIndex, aHead, mLeft - 1);
	QuickSort(aNums, aIndex, mLeft + 1, aTail);
}

int* twoSum(int* nums, int numsSize, int target) 
{
	if (numsSize < 2) {
		return NULL;
	}

	int* mIndex = (int*)malloc(numsSize * sizeof(int));

	for (int i = 0; i < numsSize; i++) {
		mIndex[i] = i;
	}

	QuickSort(nums, mIndex, 0, numsSize - 1);

	int mLeft = 0, mRight = numsSize - 1;

	if (mLeft == mRight) {
		return NULL;
	}

	int mNum = nums[mLeft] + nums[mRight];

	while (mNum != target)
	{
		if (mNum > target && --mRight > mLeft) {}
		else if (mNum < target && ++mLeft < mRight) {}
		if (mLeft == mRight)
		{
			return NULL;
		}
		mNum = nums[mLeft] + nums[mRight];
	}

	if (mNum == target) {
		int* mResult = malloc(2 * sizeof(int));
		mResult[0] = mIndex[mLeft];
		mResult[1] = mIndex[mRight];
		return mResult;
	}
	return NULL;
}

int main() 
{
	int mNums[4] = { -3,4,3,90 };

	int* mResult = twoSum(mNums, 4, 0);

	printf("[%d,%d]", mResult[0], mResult[1]);

	system("pause");

	return 1;
}

[/restab]
[/restabs]

4. Submission Details

5. Runtime Distribution