华为通软—两数之和等于给定值

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

题目的输入和输出格式是自己设计的，但是接口是统一的 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 返回5 7输入7 54 51 99 81 1 30 70100返回 1 99 30 70 排序后是1 30 51 54 70 81 99 */

如果觉得《华为通软—两数之和等于给定值》对你有帮助，请点赞、收藏，并留下你的观点哦！