Công việc của chúng tôi là viết một hàm giải bài toán hai tổng trong thời gian tuyến tính nhất.
Bài toán hai tổng
Cho một mảng các số nguyên, chúng ta phải tìm hai số sao cho chúng cộng lại thành một số mục tiêu cụ thể.
Hàm twoSum sẽ trả về các chỉ số của hai số cộng lại với mục tiêu và nếu không có hai phần tử nào cộng lại với mục tiêu, thì hàm của chúng ta sẽ trả về một mảng trống.
Giải quyết vấn đề trong O (n) thời gian
Chúng tôi sẽ sử dụng một bản đồ băm để lưu giữ bản ghi của các mục đã xuất hiện, trên mỗi lần vượt qua, chúng tôi sẽ kiểm tra xem có tồn tại bất kỳ phần tử nào trong bản đồ hay không mà khi được thêm vào phần tử hiện tại cho đến mục tiêu, nếu có, chúng tôi sẽ trả về một mảng chứa chỉ số của chúng và nếu chúng ta xem qua toàn bộ vòng lặp mà không thỏa mãn điều kiện này, chúng ta sẽ trả về một mảng trống.
Ví dụ
const arr = [2, 5, 7, 8, 1, 3, 6, 9, 4];
const sum = 10;
const twoSum = (arr, sum) => {
const map = {};
for(let i = 0; i < arr.length; i++){
const el = sum - arr[i];
if(map[el]){
return [map[el], i];
};
map[arr[i]] = i;
};
return [];
};
console.log(twoSum(arr, sum));
console.log(twoSum(arr, 12));
console.log(twoSum(arr, 13));
console.log(twoSum(arr, 14));
console.log(twoSum(arr, 24)); Đầu ra
Đầu ra trong bảng điều khiển sẽ là -
[ 2, 5 ] [ 1, 2 ] [ 1, 3 ] [ 3, 6 ] []