面试题——和为s的两个数字

1.问题描述

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出乘积最小的一对。

示例1:
输入:[2, 7, 11, 15],s=9
输出:[2, 7]或者[7, 2]

2.问题解决

(1)变治法
设a + b = s,则b = s - a,a - s / 2 = a - s / 2,b - s / 2 = s / 2 - a。
将数组中的每个数都减去s/2,进行排序,互为相反数的两个数和一定为s。

如果数组中存在多对和为s的数,我们知道和为s的两个数相差越大,乘积最小。对于递增排序的数组,减去s/2后仍然递增有序。因此,可从前向后检索,检索到两个相反数即可输出,是满足条件的。

(2)一前一后两个指针向中间遍历
不妨设两个指针start和end,若nums[start]+nums[end]的值比s大,则说明nums[end]太大,end–;若比s小,则说明nums[start]太小,start++,找到的第一对数即满足条件。

3.代码实现

(1)变治法

vector<int>& two_sum(vector<int>& nums,int target)
{int len=nums.size();double half=double(target)/2;vector<double> temp;//存储减去s/2后的数组vector<int> result;//存储结果for(int i=0;i<len;i++)temp.push_back(nums[i]-half);//每个元素都减去s/2for(int i=0;i<len;i++){double one=temp[i];for(int j=i+1;j<len;j++){if(temp[i]+temp[j]==0){result.push_back(nums[i]);result.push_back(nums[j]);return result;}}}
}

(2)指针遍历

vector<int>& two_sun(vector<int>& nums,int target)
{int start=0;int end=nums.size()-1;vector<int> result;while(start<end){if((nums[start]+nums[end])>tartget)end--;else if((nums[start]+nums[end])<tartget)start++;else{result.push_back(nums[start]);result.push_back(nums[end]);return result;}}return result;
}

4.时间复杂度分析

(1)变治法
每个元素减去s/2的时间复杂度为O(n),搜索元素时时间复杂度为O(n^2),
因此变治法的总的时间复杂度为O(n^2)。

(2)两个指针遍历法
基本操作是比较,最坏情况下比较n-1次,因此时间复杂度为O(n)。

面试题——和为s的两个数字

1.问题描述

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出乘积最小的一对。

示例1:
输入:[2, 7, 11, 15],s=9
输出:[2, 7]或者[7, 2]

2.问题解决

(1)变治法
设a + b = s,则b = s - a,a - s / 2 = a - s / 2,b - s / 2 = s / 2 - a。
将数组中的每个数都减去s/2,进行排序,互为相反数的两个数和一定为s。

如果数组中存在多对和为s的数,我们知道和为s的两个数相差越大,乘积最小。对于递增排序的数组,减去s/2后仍然递增有序。因此,可从前向后检索,检索到两个相反数即可输出,是满足条件的。

(2)一前一后两个指针向中间遍历
不妨设两个指针start和end,若nums[start]+nums[end]的值比s大,则说明nums[end]太大,end–;若比s小,则说明nums[start]太小,start++,找到的第一对数即满足条件。

3.代码实现

(1)变治法

vector<int>& two_sum(vector<int>& nums,int target)
{int len=nums.size();double half=double(target)/2;vector<double> temp;//存储减去s/2后的数组vector<int> result;//存储结果for(int i=0;i<len;i++)temp.push_back(nums[i]-half);//每个元素都减去s/2for(int i=0;i<len;i++){double one=temp[i];for(int j=i+1;j<len;j++){if(temp[i]+temp[j]==0){result.push_back(nums[i]);result.push_back(nums[j]);return result;}}}
}

(2)指针遍历

vector<int>& two_sun(vector<int>& nums,int target)
{int start=0;int end=nums.size()-1;vector<int> result;while(start<end){if((nums[start]+nums[end])>tartget)end--;else if((nums[start]+nums[end])<tartget)start++;else{result.push_back(nums[start]);result.push_back(nums[end]);return result;}}return result;
}

4.时间复杂度分析

(1)变治法
每个元素减去s/2的时间复杂度为O(n),搜索元素时时间复杂度为O(n^2),
因此变治法的总的时间复杂度为O(n^2)。

(2)两个指针遍历法
基本操作是比较,最坏情况下比较n-1次,因此时间复杂度为O(n)。