题目:
给定一个数组,找到两个总和为特定值的索引。
例如给定数组 [1, 2, 3, -2, 5, 7],给定总和 7,则返回索引 [1, 4]。
若有多组符合情况则输出索引对中小索引最小的一组。
题解:
本题可以通过暴力枚举,枚举每两个数的情况找到一个答案,但效率太低但是是可行的,更具做题的看菜吃饭原则,能做出题目就是好的,本题数据量很小所以暴力绝对是一个好的方案。
还有一种可行的方案,将数组中每个元素值和它的下标打包,然后根据元素值对打包后对象进行排序,这样就变成了一个经典的递增数组中两数之和问题,用双指针分别指向序列头部和尾部,判断头尾指针的和值与目标值的关系,如果大于目标值向前移动尾指针,如果小于目标值向后移动头指针,否则就找到了,根据题意选择小索引中最小的,然后更新头尾指针下一步指向元素位置最小的值。
#include <bits/stdc++.h>
using namespace std;
int main(){int n,k;cin>>n;vector<pair<int,int> >arr(n);for(int i=0,a;i<n;i++){cin>>a;arr[i]={a,i};}cin>>k;sort(arr.begin(),arr.end());int ans[2]={100};int l=0,r=n-1;while(l<r){if(arr[l].first+arr[r].first==k&&min(arr[l].second,arr[r].second)<ans[0]){ans[0]=min(arr[l].second,arr[r].second);ans[1]=max(arr[l].second,arr[r].second);if(arr[l+1].second<arr[r-1].second)l+=1;else r-=1;}else if(arr[l].first+arr[r].first>k)r-=1;else l+=1;}sort(arr.begin(),arr.end());cout<<ans[0]<<' '<<ans[1];return 0;
}
题后反思:
在这题中看到了leetcode上非常经典的两数之和问题,由此得到了思路,所以题目真的是相通的你做过你就容易有思路,所以没什么神秘的,积累就会越来越强。