Tìm cặp phần tử có tổng cho trước (Find pair with given sum)

Giới thiệu

Cho một mảng các số nguyên và một số mục tiêu (target sum). Nhiệm vụ là tìm hai phần tử trong mảng có tổng bằng số mục tiêu đó.

Có nhiều cách để giải quyết bài toán này. Cách đơn giản nhất là dùng hai vòng lặp lồng nhau kiểm tra tất cả các cặp, nhưng độ phức tạp là O(n²). Cách hiệu quả hơn là sắp xếp mảng rồi dùng hai con trỏ (two pointers) hoặc dùng Hash Set để tra cứu trong O(1).

Đầu vào và Đầu ra

Đầu vào: Mảng: {1, 4, 45, 6, 10, -8}, Target sum: 16
Đầu ra: Cặp tìm thấy: 6 và 10 (vì 6 + 10 = 16)

Thuật toán (Two Pointers sau khi sắp xếp)

findPair(arr, n, target)
Đầu vào: Mảng arr, kích thước n, tổng mục tiêu.
Đầu ra: True nếu tìm thấy cặp, ngược lại false.

Begin
    sắp xếp arr theo thứ tự tăng dần
    left := 0
    right := n - 1
    while left < right, do
        currentSum := arr[left] + arr[right]
        if currentSum = target, then
            return true (tìm thấy cặp arr[left], arr[right])
        else if currentSum < target, then
            left := left + 1
        else
            right := right - 1
    done
    return false
End

Thuật toán (Hash Set)

findPairHash(arr, n, target)
Đầu vào: Mảng arr, kích thước n, tổng mục tiêu.
Đầu ra: True nếu tìm thấy cặp.

Begin
    tạo HashSet rỗng
    for i := 0 to n-1, do
        complement := target - arr[i]
        if complement trong HashSet, then
            return true (tìm thấy cặp complement, arr[i])
        thêm arr[i] vào HashSet
    done
    return false
End

Ví dụ (C++)

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

// Cách 1: Two Pointers
bool findPairTwoPointers(int arr[], int n, int target) {
    sort(arr, arr + n);
    int left = 0, right = n - 1;
    while(left < right) {
        int sum = arr[left] + arr[right];
        if(sum == target) {
            cout << "Pair found: " << arr[left] << " + " << arr[right] << " = " << target;
            return true;
        } else if(sum < target) left++;
        else right--;
    }
    return false;
}

// Cách 2: Hash Set
bool findPairHash(int arr[], int n, int target) {
    unordered_set s;
    for(int i = 0; i < n; i++) {
        int complement = target - arr[i];
        if(s.find(complement) != s.end()) {
            cout << "Pair found: " << complement << " + " << arr[i] << " = " << target;
            return true;
        }
        s.insert(arr[i]);
    }
    return false;
}

int main() {
    int arr[] = {1, 4, 45, 6, 10, -8};
    int n = 6;
    int target = 16;
    cout << "Two Pointers: ";
    findPairTwoPointers(arr, n, target);
    cout << "\nHash Set: ";
    findPairHash(arr, n, target);
}

Kết quả

Two Pointers: Pair found: 6 + 10 = 16
Hash Set: Pair found: 6 + 10 = 16