[数据结构与算法]华为通软—两数之和等于给定值

首先声明，这是别人遇到的题，不是楼主遇到的。在此总结是为了准备自己是面试手撕代码。

题目的输入和输出格式是自己设计的，但是接口是统一的 int* twoSum(int* nums, int numsSize, int target)；

题目：

给定一个数组和一个目标值，输出数组中所有满足两项之和等于目标值的数对。

例如输入：
4
5 7 1 20
12
则输出：
5 7

例如输入：
7?
54 51 99 81 1 30 70
100
则输出：
1 99 30 70

函数接口为：
int* twoSum(int* nums, int numsSize, int target)；

答案：

思路有三种。第一种是遍历，简单粗暴但是不够精巧。第二种是先对数组排序，然后双指针法，当（左+右<目标）时左指针右移，当（左+右＞目标）时右指针左移，当（左+右=目标）时左指针右移且右指针左移。第三种是使用哈希表。此处仅展开第二种排序+双指针的方法。

/*找出一个数组中的两个数字，让这两个数字之和等于一个给定的值。
假设数组中的都是各不相等的整数。若有多组解则都输出。
核心是函数int* twoSum(int* nums, int numsSize, int target) 
*/
#include<stdio.h>
#include<stdlib.h> 
int* twoSum(int* nums, int numsSize, int target);

int main (){
	int n;
	scanf("%d",&n);
	int nums[n],i;
	for (i=0;i<n;i++) {
		scanf("%d",&nums[i]);
	}
	int target;
	scanf("%d",&target);
	
	int* res=twoSum(nums,n,target);
	for (i=0;i<n&&res[i]<=target;i++) printf("%d ",res[i]);
    free(res);//记得把空间还回去
	if(i==0){
		printf("NULL");
	} 
	return 0;
}

int* twoSum(int* nums, int numsSize, int target) {
	int *res=(int*)malloc(numsSize*sizeof(int));
    //因为要返回这个数组，如果不malloc会返回临时变量，这是不对的。
	int i;
	for (i=0;i<numsSize;i++) res[i]=target+1;
	int j,temp;
	
	//一个插入排序 
	for (i=1;i<numsSize;i++) {
		temp=nums[i];
		for (j=i;j>0&&nums[j-1]>temp;j--)
			nums[j]=nums[j-1];
		nums[j]=temp;
	}
	
	int index=0,left=0,right=numsSize-1;
	while (left<right) {
		if (nums[left]+nums[right]<target) left++;
		else if (nums[left]+nums[right]>target) right--;
		else {
			//如果相等了，左右指针都要变，否则无限循环了 
			res[index++]=nums[left++];  
			res[index++]=nums[right--];
		}
	}
	return res;
}

/*测试用例
输入
4 
1 5 7 20
12
返回5 7

输入
7 
54 51 99 81 1 30 70
100
返回 1 99 30 70 
排序后是1 30 51 54 70 81 99 
*/