文章

74

粉丝

0

获赞

94

访问

8.2k

头像
三个数的和 (双指针)题解:
P5286 武汉大学2024年机试题
发布于2025年8月23日 21:38
阅读数 37

#include<iostream>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;

int main(){

    int n;
    while(cin >> n){
        vector<int> nums(n);
        for(int i = 0; i < n; i ++) cin >> nums[i];

        sort(nums.begin(), nums.end()); // 排序

        for(int i = 0; i < n - 2; i ++){
            int x = nums[i];

            if(i > 0 && nums[i] == nums[i - 1]) continue; // 去除重复答案

            int l = i + 1;
            int r = nums.size() - 1;
            int target = -x;
			
			if(nums[l] + nums[l + 1] > target) break; // 利用从小到大排序性质优化1
			if(nums[r - 1] + nums[r] < target) continue; // 利用从小到大排序性质优化2
			
            while(l < r) {
                if(nums[l] + nums[r] < target) l ++;
                else if(nums[l] + nums[r] > target) r --;
                else {
                    cout << x << ' ' << nums[l ++] << ' ' << ...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发