织梦做不了视频网站,北京搭建公司,wordpress 模板怎么用,seo哪家强题目#xff1a;
给定一个数组#xff0c;找到两个总和为特定值的索引。
例如给定数组 [1, 2, 3, -2, 5, 7]#xff0c;给定总和 7#xff0c;则返回索引 [1, 4]。
若有多组符合情况则输出索引对中小索引最小的一组。
题解:
本题可以通过暴力枚举#xff0c;枚举每两…题目
给定一个数组找到两个总和为特定值的索引。
例如给定数组 [1, 2, 3, -2, 5, 7]给定总和 7则返回索引 [1, 4]。
若有多组符合情况则输出索引对中小索引最小的一组。
题解:
本题可以通过暴力枚举枚举每两个数的情况找到一个答案但效率太低但是是可行的更具做题的看菜吃饭原则能做出题目就是好的本题数据量很小所以暴力绝对是一个好的方案。
还有一种可行的方案将数组中每个元素值和它的下标打包然后根据元素值对打包后对象进行排序这样就变成了一个经典的递增数组中两数之和问题用双指针分别指向序列头部和尾部判断头尾指针的和值与目标值的关系如果大于目标值向前移动尾指针如果小于目标值向后移动头指针否则就找到了根据题意选择小索引中最小的然后更新头尾指针下一步指向元素位置最小的值。
#include bits/stdc.h
using namespace std;
int main(){int n,k;cinn;vectorpairint,int arr(n);for(int i0,a;in;i){cina;arr[i]{a,i};}cink;sort(arr.begin(),arr.end());int ans[2]{100};int l0,rn-1;while(lr){if(arr[l].firstarr[r].firstkmin(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[l1].secondarr[r-1].second)l1;else r-1;}else if(arr[l].firstarr[r].firstk)r-1;else l1;}sort(arr.begin(),arr.end());coutans[0] ans[1];return 0;
} 题后反思
在这题中看到了leetcode上非常经典的两数之和问题由此得到了思路所以题目真的是相通的你做过你就容易有思路所以没什么神秘的积累就会越来越强。
