首页 > 代码库 > 返回数组中元素之和为输入值的元素的下标（以1为基）
返回数组中元素之和为输入值的元素的下标（以1为基）
Leetcode中原题：Two Sum
给定一个整数数组，找出其中和等于给定目标值的数的下标（数组第一个元素的下标是1），第一个下标必须比第二个下标小，假定此题只有唯一解。
例：
输入：numbers={2, 7, 11, 15}, target=9
输出：index1=1, index2=2
思路1：两层循环，外层循环从0到倒数第二个元素，里层循环，从当前外层循环下标的下一个值开始一直到数组结尾，复杂度O(n2)，超时。
思路2：如果数组是有序的，显然有更好的做法。使用常用的效率比较高的排序算法，归并排序，堆排序等，时间复杂度为O(nlogn). 因为我们需要记录原始数组中的下标，所以不能在原始数组上进行排序，需要拷贝原始数组，在拷贝数组上进行排序。排完序后需要做两件事：
1）找出和为目标值的两个元素
2）找出这两个元素在原始数组中的下标。
其中，操作1）设定两个指针，分组指向数组的头部和尾部，计算指针所指值的和，如果两者之和大于目标值，则将尾部指针前移，如果两者之和小于目标值，则将首部指针后移，这样找到所求元素的时间复杂度是O(n)。
操作2）只需要遍历原始数组一遍，就可以求得相应下标，对应的时间复杂度为O(n)。
综合以上求解过程，整的时间复杂度为O(nlogn)+O(n)+O(n)=O(nlogn).
源代码如下：
class Solution {public: vector<int> twoSum(vector<int> &numbers, int target) { vector<int> temp(numbers); vector<int> ret; merge_sort(temp,0,temp.size()-1); // 对拷贝数组进行归并排序 int i = 0,j=temp.size()-1,k; int temp_first,temp_second; // 记录所求元素值的临时变量
// 查找排序后数组中满足和为目标值的元素 while(i<j) { if((temp[i]+temp[j])<target) { i++; } else if((temp[i]+temp[j])>target) { j--; } else { temp_first = temp[i]; temp_second = temp[j]; break; } } k=0;
// 遍历原始数组，找出相应元素的下标 for(k;k!=numbers.size();k++) { if(numbers[k]==temp_first||numbers[k]==temp_second) { ret.push_back(k+1); } } return ret; } void merge_sort(vector<int> &ivec,int ,vector<int>::size_type size); void merge(vector<int>&ivec,int p,int q,int r);};void Solution::merge_sort(vector<int> &ivec,int p ,vector<int>::size_type r){ int q; if(p<r) { q = (p+r)/2; merge_sort(ivec,p,q); merge_sort(ivec,q+1,r); merge(ivec,p,q,r); }}void Solution::merge(vector<int>&ivec,int p,int q,int r){ int i=0,j=0,k=p; vector<int>::iterator iter = ivec.begin(); vector<int> lvec(iter+p,iter+q+1); vector<int> rvec(iter+q+1,iter+r+1); while(i<lvec.size()&&j<rvec.size()) { if(lvec[i]<=rvec[j]) ivec[k++]=lvec[i++]; else ivec[k++]=rvec[j++]; } if(i<lvec.size()) { for(k;k<=r;k++,i++) ivec[k]=lvec[i]; } else { for(k;k<=r;k++,j++) ivec[k]=rvec[j]; }}
返回数组中元素之和为输入值的元素的下标（以1为基）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。