两数之和与杨氏矩阵

两数之和

暴力解法

解题思路：

两个for循环嵌套，暴力枚举两个数字。

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

for循环+二分查找

时间复杂度：$O(nlogn)$

空间复杂度：$O(1)$

for循环+哈希函数

时间复杂度：$O(n)$

空间复杂度：$O(n)$

双指针法

左右端分别一个指针，求和结果与目标比较，偏大，右指针左移一位，偏小，左指针右移一位。

时间复杂度：$O(n)$

空间复杂度：$O(1)$

代码实现（C++）

#include <iostream>
using namespace std;

int main() {
    int n, t, num[100005];
    for (int i = 1; i <=n; i++) {
        cin >> num[i];
    }
    int l = 1, r = n;
    while (l < r) {
        int sum = num[l] + num[r];
        if (t == sum) {
            cout << l << " " << r << endl;
            return 0;
        }
        if (t < sum) {
            r--;
        } else {
            l++;
        }
    }
    cout << -1 << endl;
    return 0;
}

扩展：杨氏矩阵的查找

杨氏矩阵：从左到右，从上到下，数组元素的值单调递增。

核心思想：从左下角或右上角开始比较查找。

时间复杂度：$O(n+m)$

代码实现（C++）

#include <iostream>
using namespace std;

int main() {
    int n , m , num[105][105], t;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
             cin >> num[i][j];
        }    
    }
    cin >> t;
    int x = n, y = 1;
    while (x >= 1 && y <= m) {
        if (num[x][y] == t) {
            cout << x << " " << y << endl;
            return 0;
        }
        if (num[x][y] > t) {
            x--;
        } else {
            y++;
        }
    }
    cout<< -1 << endl;
    return 0;    
}

杨氏矩阵的查找思想与双指针法其实异曲同工。