問題描述

給你一個包含 $n$ 個整數的陣列，你的任務是找出三個位於不同位置的數，使得它們的總和為 $x$

練習題

CSES - Sum of Three Values

連結： https://cses.fi/problemset/task/1641/

先由小到大排序後，從最小的值 $k$ 開始遍歷，利用 Two-Pointer 找解，左指標指向比 $i$ 大的那項 $j$，右指標指向最後一項 $k$，若 $i$ + $j$ + $k$ 的總和等於 $x$，則輸出並結束；否則若大於 $x$，代表我們需要讓總和小一點，把右指標往左移；如若不然，則要讓總和大一點，把左指標往右移。

時間複雜度 $O(n^2)$

完整程式碼

#include <bits/stdc++.h>
using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}
 
int main() {
    int n, x;
    cin >> n >> x;
    pair<int, int> arr[5005];
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first;
        arr[i].second = i + 1;
    }
    sort(arr, arr + n, cmp);
    for (int i = 0; i < n - 2; i++) {
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int sum = arr[i].first + arr[left].first + arr[right].first;
            if (sum == x) {
                cout << arr[i].second << " " << arr[left].second << " " << arr[right].second;
                return 0;
            } else if (sum < x) {
                left++;
            } else {
                right--;
            }
        }
    }
    cout << "IMPOSSIBLE";
}

CSES - Sum of Four Values

連結：https://cses.fi/problemset/task/1642/

跟前一題很像，只是這裡我們要遍歷兩個值，才用 Two-Pointer 找符合的答案。

時間複雜度 $O(n^3)$

完整程式碼

#include <bits/stdc++.h>
using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}
 
int main() {
    int n, x;
    cin >> n >> x;
    pair<int, int> arr[5005];
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first;
        arr[i].second = i + 1;
    }
    sort(arr, arr + n, cmp);
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            int left = j + 1;
            int right = n - 1;
            while (left < right) {
                int sum = arr[i].first + arr[j].first + arr[left].first + arr[right].first;
                if (sum == x) {
                    cout << arr[i].second << " " << arr[j].second << " " << arr[left].second << " "
                         << arr[right].second;
                    return 0;
                } else if (sum < x) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    cout << "IMPOSSIBLE";
}