Cách tìm nhóm 3 phần tử trong mảng có tổng bằng target trong JavaScript

Viết hàm threeSum() nhận mảng số và target sum. Kiểm tra có 3 số nào cộng = target không, có thì trả về mảng chỉ số 3 số đó, không thì -1.

Cách tiếp cận

Viết helper twoSum() O(n) time/space: hashmap lưu giá trị->index, tìm target - current. Hàm threeSum() duyệt từng phần tử làm số thứ 3, gọi twoSum trên mảng với target - arr[i], nếu tìm thấy và index không trùng => trả về 3 index. Độ phức tạp O(N^2).

Ví dụ

const arr = [1,2,3,4,5,6,7,8];

const twoSum = (arr, sum) => {
  const map = {};
  for (let i = 0; i < arr.length; i++) {
    if (map[sum - arr[i]]) {
      return [map[sum - arr[i]], i];
    }
    map[arr[i]] = i;
  }
  return -1;
};

const threeSum = (arr, sum) => {
  for (let i = 0; i < arr.length; i++) {
    const indices = twoSum(arr, sum - arr[i]);
    if (indices !== -1 && !indices.includes(i)) {
      return [i, ...indices];
    }
  }
  return -1;
};

console.log(threeSum(arr, 9));
console.log(threeSum(arr, 8));
console.log(threeSum(arr, 13));
console.log(threeSum(arr, 23));

Kết quả

Đầu ra trong console sẽ là:

[ 0, 2, 4 ] [ 0, 2, 3 ] [ 0, 4, 6 ] -1