Tìm 2 phần tử có tổng gần bằng 0 nhất

Mục lục

1 Cách 1 Sử dụng 2 vòng lặp
2 Cách 2 Sắp xếp mảng

Cho một mảng số nguyên gồm n phần tử. Tìm 2 phần tử có tổng gần bằng 0 nhất.

Ví dụ:

Input: arr[] = {1, 60, -10, 70, -80, 85};
Output: {-80, 85}

Thật chất đề bài trên chúng ta có thể hiểu theo cách khác đó chính là tìm cặp số có trị tuyệt đối nhỏ nhất

Cách 1 Sử dụng 2 vòng lặp

Sử dụng 2 vòng lặp để tìm tất cả các tổng của một số với các số còn lại trong mảng, sau đó lấy trị tuyệt đối để so sánh.

public class Main {

    public static void findMinSumAbs(int[] arr, int n) {
        if (n == 2) {
            System.out.println("Khong tim thay");
            return;
        }

        int e1 = -1, e2 = -1, minSum = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(arr[i] + arr[j]) < minSum) {
                    minSum = Math.abs(arr[i] + arr[j]);
                    e1 = arr[i];
                    e2 = arr[j];
                }
            }
        }

        System.out.println("{" + e1 + "; " + e2  +"}");
    }

    public static void main(String[] args) {
        int arr[] = {1, 60, -10, 70, -80, 85};
        findMinSumAbs(arr, arr.length);
    }
}

Output: {-80, 85}

Độ phức tạp: O(n²)

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

Sau khi mảng đã được sắp xếp, cặp số có trị tuyệt đối nhỏ nhất sẽ nằm cạnh nhau.

B1: Sắp xếp mảng
B2: Khởi tạo e1 = 0; e1 = n – 1, min_e1 = 0, min_e2 = n – 1. minSum = Interger.MaxValue
B3: While e1 < e2
1. sum = arr[e1] + arr[e2]
2. if |sum| < minSum thì minSum = |arr[e1] + arr[e2]|; min_e1 = e1; min_e2 =e2
3. sum < 0 thì e1++
4. else e2–;
B4: Kết quả arr[e1] và arr[e2]

import java.util.Arrays;
import java.util.Map;

public class Main {

    public static void findMinSubAbsSort(int[] arr, int n) {
        if (n == 2) {
            System.out.println("Khong tim thay");
            return;
        }
        
        // Sắp xếp mảng
        Arrays.sort(arr);

        // Khởi tạo 
        int e1 = 0, e2 = n-1, minSum = Integer.MAX_VALUE;
        // Lưu vị trí cặp số có trị tuyệt đối nhỏ nhất 
        int min_e1 = 0, min_e2 = n-1;
        // Duyệt và tìm kiếm cặp số thoả điều kiện 
        while (e1 < e2) {
            int sum = arr[e1] + arr[e2];
            if (Math.abs(sum) < Math.abs(minSum)) {
                minSum = sum;
                min_e1 = e1;
                min_e2 = e2;
            }
            if (sum < 0)
                e1++;
            else e2--;
        }
        // Xuất kết quả 
        System.out.println("{" + arr[min_e1] + "; " + arr[min_e2]  +"}");
    }
    public static void main(String[] args) {
        int arr[] = {1, 60, -10, 70, -80, 85};
        findMinSubAbsSort(arr, arr.length);
    }
}

Output: {-80, 85}

Độ phức tạp: O(nlogn)

Độ phức tạp của cách 2 phụ thuộc vào thuật toán sắp xếp mà các bạn chọn nhé.

Link đề bài: https://www.geeksforgeeks.org/two-elements-whose-sum-is-closest-to-zero/