Bài toán Two Sum thời gian tuyến tính trong JavaScript

Viết hàm nhận mảng số và target sum. Tìm chỉ số hai số (có thể không liên tiếp) cộng bằng target. Yêu cầu O(n) - một lần duyệt.

Dùng Map lưu số đã duyệt, nếu gặp số bù thì trả về ngay.

Ví dụ

const arr = [1, 3, 5, 7, 9, 11]; 
const target = 16; 
const twoSum = function(arr, target) { 
  const map = new Map(); 
  for(let i = 0; i < arr.length; i++) { 
    let num = arr[i]; 
    if(map.get(num) === undefined){ 
      map.set(target - num, i); 
    } else { 
      return [map.get(num), i]; 
    }; 
  }; 
}; 
console.log(twoSum(arr, target));

Kết quả

Kết quả in ra console:

[3, 4]