Cho một mảng arr[] và một số nguyên X, kiểm tra xem trong mảng có cặp nào có tổng bằng X.

Cách 1: Sử dụng 2 vòng lặp để liệt kê tất cả các tập có thể có tử mảng rồi đem so sánh với tổng.

B1: Loop i từ 0 -> n - 1
B2: Với mỗi giá trị i, loop j từ i + 1 -> n
      + Nếu arr[i] + arr[j] == sum thì return true
B3: Return false nếu không có cặp nào có tổng bằng sum

Đối với cách 1 thì độ phức tạp là θ(n²).

public class Main {

    public static void main(String[] args) {
        int[] arr = {1, 4, 45, 6, 10, -8};
        int sum = 16;
        int size_arr = arr.length;
        System.out.println(checkPairSum(arr, size_arr, sum));
    }

    static boolean checkPairSum(int[] arr, int size_arr, int sum) {
        for (int i = 0; i < size_arr - 1; i++)
            for (int j = i + 1; j < size_arr; j++)
                if (arr[i] + arr[j] == sum)
                    return true;
        return false;
    }
}

Output: true

Cách 2: Sắp xếp mảng

B1: Sắp xếp mảng tăng dần
B2: Khởi tạo index của 2 cặp số cần tìm
    1. Phần tử ngoài cùng bên trái: l = 0
    2. Phần tử ngoài cùng bên phải: r = size_arr - 1
B3: Loop while (l < r)
    If (arr[l] + arr[r] == sum) return true
    Else if (arr[l] + arr[r] > sum) r--
    Else l++
B4: Return false nếu không có cặp nào có tổng bằng sum

­

Độ phức tạp của cách giả này phụ thuộc vào thuật toán sắp xếp chúng ta chọn, các bạn có thể tham khảo các thuật toán tại đây. Ví dụ dùng quicksort để sắp xếp cho bài này, với độ phức tạp cho trường hợp tốt nhất là θ(nlog(n)), xấu nhất là θ(n²).

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        int[] arr = {1, 4, 45, 6, 10, -8};
        int sum = 16;
        int size_arr = arr.length;
        System.out.println(checkPairSumWayOne(arr, size_arr, sum));
        System.out.println(checkPairSumWayTwo(arr, size_arr, sum));

    }

    static boolean checkPairSumWayTwo(int[] arr, int size_arr, int sum) {
        Arrays.sort(arr);
        int l = 0, r = size_arr - 1;
        while (l < r) {
            if (arr[l] + arr[r] == sum)
                return true;
            else if (arr[l] + arr[r] > sum)
                r--;
            else
                l++;
        }
        return false;
    }
}

Output: true

Cách 3: Sử dụng HashSet

B1: Khởi tạo một HashSet s
B2: Loop i từ 0 -> n - 1
    + Nếu (sum - arr[i]) có trong s thì in ra cặp giá trị thoả(arr[i], sum - arr[i]
    + Thêm arr[i] vào s

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        int[] arr = {1, 4, 45, 6, 10, -8};
        int sum = 16;
        int size_arr = arr.length;
        checkPairSumWayThree(arr, size_arr, sum);
    }

   static void checkPairSumWayThree(int[] arr, int size_arr, int sum) {
        Set<Integer> s = new HashSet<>();

        for (int i = 0; i < size_arr; i++) {
            int tmp = sum - arr[i];
            if (s.contains(tmp) && tmp > 0)
                System.out.println("Cap gia tri thoa: (" + arr[i] + ", " + tmp + ")"  );
            s.add(arr[i]);
        }
    }

}

Output: Cap gia tri thoa: (10, 6)

Link full source code: source-code

Nguồn tham khảo: geeksforgeeks