AcWing 1532. 找硬币【双指针算法详解】

ゝ一纸荒年。 2021-07-24 13:56 342阅读 0赞

### 题目 ###

伊娃喜欢从整个宇宙中收集硬币。

有一天，她去了一家宇宙购物中心购物，结账时可以使用各种硬币付款。

但是，有一个特殊的付款要求：每张帐单，她只能使用恰好两个硬币来准确的支付消费金额。

给定她拥有的所有硬币的面额，请你帮她确定对于给定的金额，她是否可以找到两个硬币来支付。

**输入格式**  
第一行包含两个整数 N 和 M，分别表示硬币数量以及需要支付的金额。

第二行包含 N 个整数，表示每个硬币的面额。

**输出格式**  
输出一行，包含两个整数 V1,V2，表示所选的两个硬币的面额，使得 V1≤V2 并且 V1+V2=M。

如果答案不唯一，则输出 V1 最小的解。

如果无解，则输出 No Solution。

**数据范围**  
1≤N≤105,  
1≤M≤1000  
**输入样例1：**  
8 15  
1 2 8 7 2 4 11 15  
**输出样例1：**  
4 11  
**输入样例2：**  
7 14  
1 8 7 2 4 11 15  
**输出样例2：**  
No Solution

### 什么是双指针算法？ ###

**简介**  
双指针算法应用非常广泛，而它能够拿出来作为一种效率较高的算法是因为它和普通的暴力搜索相比，为组合项固定了一些顺序，直接排除了一些组合选项。其思路就是，每次两个指针里面，一个指针负责循环遍历，另一个指针负责检查条件，配合。  
**模板**

for (int i = 0, j = 0; i < n; i ++ )
    { 
        while (j < i && check(i, j)) j ++ ;
    
        // 具体问题的逻辑
    }
    常见问题分类：
        (1) 对于一个序列，用两个指针维护一段区间
        (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

### 使用条件有哪些？ ###

能用双指针算法的地方一定可以暴力求解，我们先想出一个暴力解法，再考虑使用双指针算法优化。如果可以用双指针来维护一段区间，**那么这段区间一定要是单调的**。因为只有满足单调性，我们才可以为组合项固定一些顺序，直接排除了另一些组合选项。

### 解题思路 ###

对于这道题，先想出暴力解法。

for (int i = 0; i < n; i++)
    { 
    	for (int j = 0; j < i; j++)
    	{ 
    		if (a[i] + a[j] == m) //更新答案
    		{ 
    		
    		}
    	}
    }

时间复杂度为 `O(n^2)` 很容易超时。

### 考虑双指针算法优化 ###

先将数组排序，使它**有序**。

然后定义两个指针`i`,`j` 。`i`指向数组开头，`j`指向数组结尾。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

当两个指针未相交，并且`a[i]+a[j]>m` 说明 `a[j]`取大了，向左移动`j`指针，使其两数之和`a[i] +a[j]`减小。 即执行 `while (i<j&&a[i] + a[j]>m) j--;` 直到`a[i]+a[j]<=m` 退出循环 。

然后判断 `a[i] +a[j]` 是否等于 `m` ,若不等于 说明 `a[i]`取小了，向右移动`i`指针 ，使两数之和`a[i] +a[j]`增大。

继续上述操作 直到 `a[i] +a[j] ==m`时，我们记录答案。

sort(a, a + n);
    	for (int i = 0, j = n - 1; i < j; i++)
    	{ 
    		while (i<j&&a[i] + a[j]>m) j--;
    		if (i < j&&a[i] + a[j] == m)
    		{ 
    			//记录答案
    		}
    	}

由于`i`指针或者`j`指针只能向一个方向移动，因此`i++`或者 `j--`最多执行`n`次，时间复杂度为 `O(n)`。

### 完整代码 ###

#include<iostream>
    #include<algorithm>
    using namespace std;
    const int N = 1e5 + 10;
    int a[N];
    int main()
    { 
    	int n, m;
    	cin >> n >> m;
    	for (int i = 0; i < n; i++) cin >> a[i];
    	int v1, v2, flag = 0;
    	sort(a, a + n);
    	for (int i = 0, j = n - 1; i < j; i++)
    	{ 
    		while (i<j&&a[i] + a[j]>m) j--;
    		if (i < j&&a[i] + a[j] == m)
    		{ 
    			v1 = a[i];
    			v2 = a[j];
    			flag = 1;
    			break;
    		}
    	}
    	if (flag) cout << v1 << ' ' << v2 << endl;
    	else cout << "No Solution" << endl;
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/a7a09eac626541f09b5331edc304c00d.png