Tìm Các Cặp Có Tổng Bằng Một Giá Trị Cho Trước Trong Một Mảng JavaScript

Để tìm tất cả các cặp số trong một mảng có tổng bằng một giá trị cho trước trong JavaScript, bạn có thể sử dụng nhiều phương pháp khác nhau. Một phương pháp đơn giản là sử dụng hai vòng lặp lồng nhau để kiểm tra tất cả các cặp phần tử trong mảng. Tuy nhiên, phương pháp này có độ phức tạp là O(n^2). Một phương pháp hiệu quả hơn là sử dụng một cấu trúc dữ liệu như đối tượng hoặc tập hợp để lưu trữ các phần tử đã duyệt qua, giúp giảm độ phức tạp xuống O(n).

Phương pháp 1: Sử dụng hai vòng lặp lồng nhau

Ví dụ:

function findPairs(arr, targetSum) {
    let pairs = [];
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[i] + arr[j] === targetSum) {
                pairs.push([arr[i], arr[j]]);
            }
        }
    }
    return pairs;
}

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let target = 10;
console.log(findPairs(array, target)); 
// Output: [ [ 1, 9 ], [ 2, 8 ], [ 3, 7 ], [ 4, 6 ] ]

Phương pháp 2: Sử dụng đối tượng để lưu trữ các phần tử đã duyệt qua

Ví dụ:

function findPairs(arr, targetSum) {
    let pairs = [];
    let seen = {};

    for (let num of arr) {
        let complement = targetSum - num;
        if (seen[complement]) {
            pairs.push([num, complement]);
        }
        seen[num] = true;
    }

    return pairs;
}

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let target = 10;
console.log(findPairs(array, target)); 
// Output: [ [ 9, 1 ], [ 8, 2 ], [ 7, 3 ], [ 6, 4 ] ]

Phương pháp 3: Sử dụng Set để lưu trữ các phần tử đã duyệt qua

Ví dụ:

function findPairs(arr, targetSum) {
    let pairs = [];
    let seen = new Set();

    for (let num of arr) {
        let complement = targetSum - num;
        if (seen.has(complement)) {
            pairs.push([num, complement]);
        }
        seen.add(num);
    }

    return pairs;
}

let array = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let target = 10;
console.log(findPairs(array, target)); 
// Output: [ [ 9, 1 ], [ 8, 2 ], [ 7, 3 ], [ 6, 4 ] ]

Giải Thích:

1. Phương pháp 1:

   • Duyệt qua tất cả các cặp phần tử trong mảng bằng hai vòng lặp lồng nhau.
   • Kiểm tra nếu tổng của hai phần tử bằng giá trị cho trước, thì thêm cặp đó vào mảng kết quả.

2. Phương pháp 2:

   • Sử dụng một đối tượng để lưu trữ các phần tử đã duyệt qua.
   • Duyệt qua mảng, với mỗi phần tử, tính phần bù để đạt tổng bằng giá trị cho trước.
   • Nếu phần bù đã tồn tại trong đối tượng, thêm cặp vào mảng kết quả.
   • Thêm phần tử hiện tại vào đối tượng đã duyệt qua.

3. Phương pháp 3:

   • Tương tự như phương pháp 2 nhưng sử dụng Set để lưu trữ các phần tử đã duyệt qua.
   • Duyệt qua mảng, với mỗi phần tử, tính phần bù để đạt tổng bằng giá trị cho trước.
   • Nếu phần bù đã tồn tại trong Set, thêm cặp vào mảng kết quả.
   • Thêm phần tử hiện tại vào Set.