Có cách hiệu quả hơn để giải bài "2 Sum" này không JavaScript

Viết hàm giải bài toán Two Sum trong thời gian tuyến tính tối đa.

Bài toán Two Sum

Cho mảng số nguyên, tìm hai số cộng lại bằng target cho trước. Hàm twoSum trả về chỉ số hai số đó, nếu không có thì trả về mảng rỗng.

Giải O(n) time

Dùng hashmap (object) lưu các phần tử đã gặp. Mỗi lượt kiểm tra xem target - current có trong map không, nếu có trả về chỉ số, nếu hết vòng lặp không thấy thì trả về [].

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));

Kết quả

Đầu ra trong console sẽ là:

[ 2, 5 ] [ 1, 2 ] [ 1, 3 ] [ 3, 6 ] []