您的位置:首页 > 娱乐 > 明星 > 蓝桥杯 经典算法题 查找两个总和为特定值的索引

蓝桥杯 经典算法题 查找两个总和为特定值的索引

2024/10/6 8:24:51 来源:https://blog.csdn.net/zaqjkl/article/details/139845239  浏览:    关键词:蓝桥杯 经典算法题 查找两个总和为特定值的索引

题目:

给定一个数组,找到两个总和为特定值的索引。

例如给定数组 [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上非常经典的两数之和问题,由此得到了思路,所以题目真的是相通的你做过你就容易有思路,所以没什么神秘的,积累就会越来越强。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com