Sum of Four Values(sorting and searching)

题目描述

You are given an array of n integers, and your task is to find four values (at distinct positions) whose sum is x.

输入

The first input line has two integers n and x: the array size and the target sum.
The second line has n integers a1,a2,...,an: the array values.
Constraints
1 ≤ n ≤ 1000
1 ≤ x,ai ≤ 

输出

Print four integers: the positions of the values. If there are several solutions, you may print any of them. If there are no solutions, print IMPOSSIBLE.

样例输入

8 15
3 2 5 8 1 3 2 3

样例输出

2 4 6 7

思路分析

4-sum问题。

3-sum问题是一层循环+双指针，而4-sum问题是双层循环+双指针。

1.创建一个存储 pair 类型的 vector，其中 pair 的第一个元素存储数组元素的值，第二个元素存储该元素在原数组中的下标(1-based indexing)。

2.对 vector 按照元素值进行排序，这样方便后续使用双指针法，以及避免不必要的遍历。

3.第一层循环（0~n-4）：遍历排序后的 vector，对于每个元素，将问题转化为在剩余元素中寻找三个数，使得它们的和等于 x 减去当前元素的值。

4.第二层循环（j从i+1~n-3）：遍历 vector，对于每个元素，将问题转化为在剩余元素中寻找两个数，使得它们的和等于 x 减去当前两个元素的值。对于每一次转化后的两数和问题，使用双指针来求解。

5. 双指针求解两数和问题：区间为[j+1,n-1]。如果找到满足条件的两个数，输出当前四个元素在原数组中的下标，然后终止程序。

6.如果在遍历完所有可能的组合后都没有找到满足条件的四个数，最后输出 "IMPOSSIBLE"。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x,a;
vector<pair<int,int>>v;
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>x;for(int i=1;i<=n;i++){cin>>a;v.push_back({a,i});}sort(v.begin(),v.end());for(int i=0;i<n-3;i++){if(v[i].first>=x)break;for(int j=i+1;j<n-2;j++){if(v[i].first+v[j].first>=x)break;int l=j+1,r=n-1;int target=x-v[i].first-v[j].first;while(l<r){if(v[l].first+v[r].first==target){cout<<v[i].second<<" "<<v[j].second<<" "<<v[l].second<<" "<<v[r].second;return 0;}else if(v[l].first+v[r].first<target){l++;}else{r--;}}}}cout<<"IMPOSSIBLE";return 0;
}