数组元素的目标和（双指针算法）

女爷i 2023-03-04 08:14 18阅读 0赞

**上一篇博客[LeetCode 3.无重复字符的最长子串（滑动窗口、双指针）][LeetCode 3.]**

>  写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。这篇博客来记录一下数组元素的目标和题目的解题思路。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  数据范围
     *  输入样例
     *  输出样例
 *  题解
 *   *  暴力算法（TLE）
     *   *  代码
         *  提交结果
     *  双指针算法（正解）
     *   *  解题思路
         *  解题代码
         *  时间复杂度
         *  提交结果

# 题目信息 #

原题链接：[数组元素的目标和][Link 1]

## 题目描述 ##

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。请你求出满足A\[i\] + B\[j\] = x的数对(i, j)。

数据保证有唯一解。

## 输入格式 ##

第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。  
 第二行包含n个整数，表示数组A。  
 第三行包含m个整数，表示数组B。

## 输出格式 ##

共一行，包含两个整数 i 和 j。

## 数据范围 ##

数组长度不超过100000。  
 同一数组内元素各不相同。  
 1 ≤ 数组元素 ≤ 10^9

## 输入样例 ##

> 4 5 6  
> 1 2 4 7  
> 3 4 6 8 9

## 输出样例 ##

> 1 1

# 题解 #

## 暴力算法（TLE） ##

首先解释一下为什么暴力算法不可以通过该题目，因为题目给出的数据范围为 **10^5**，但是题目给出的运行时间只有 **1s**。但是时间复杂度为 **O(n^2)** 的算法只能解决数据量大约在 10^4级别的数据。很明显暴力算法会超时。

### 代码 ###

#include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    int A[N], B[N];
    int n, m, x;
    
    int main() { 
        cin >> n >> m >> x;
        for (int i = 0; i < n; i++) scanf("%d", &A[i]);
        for (int i = 0; i < m; i++) scanf("%d", &B[i]);
        
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (A[i] + B[j] == x) { 
                    cout << i << " " << j;
                    return 0;
                }
            }
        }
        
    }

### 提交结果 ###

> 代码提交状态： `Time Limit Exceeded`

## 双指针算法（正解） ##

### 解题思路 ###

因为题目说两个数组是**升序排序的有序数组**，所以我们可以利用这个单调性找到使每一个 A\[i\] 满足 A\[i\] + B\[j\] < x 的最小的 j，找到最小的B\[j\] 之后使 i 向后移动直到找到答案。

### 解题代码 ###

#include<iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    int A[N], B[N];
    int n, m, x;
    
    int main() { 
        cin >> n >> m >> x;
        for (int i = 0; i < n; i++) scanf("%d", &A[i]);
        for (int i = 0; i < m; i++) scanf("%d", &B[i]);
        
        for (int i = 0, j = m - 1; i < n; i++) { 
            while (j >= 0 && A[i] + B[j] > x) j--;
            if (A[i] + B[j] == x) { 
                cout << i << " " << j;
                break;
            }
        }
        
        return 0;
    }

### 时间复杂度 ###

因为数组A，B的长度分别为 n, m，在遍历的过程中两个数组最多只会被遍历一次，所以时间复杂度为**O(n + m)**，也就是**O(n)**。

### 提交结果 ###

> 代码提交状态： `Accepted`

--------------------

> 未完待续，持续更新中……  
> ![冲鸭！][20200802160443720.png]

[LeetCode 3.]: https://ac-fun.blog.csdn.net/article/details/107730618
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[Link 1]: https://www.acwing.com/problem/content/802/
[20200802160443720.png]: /images/20230208/258ab56a77d942439d8fad2c8a8b5352.png