Cách tìm một nhóm ba phần tử trong một mảng có tổng của nó bằng một số JavaScript tổng mục tiêu

Chúng ta phải viết một hàm, chẳng hạn như threeSum () nhận một mảng Numbers và một targetum. Nó kiểm tra xem có tồn tại bất kỳ ba số nào trong mảng mà cộng thành tổng mục tiêu hay không, nếu tồn tại ba số như vậy trong mảng, thì nó sẽ trả về các chỉ số của chúng trong một mảng, ngược lại nó sẽ trả về -1.

Phương pháp tiếp cận

Cách tiếp cận rất đơn giản, Đầu tiên chúng ta sẽ viết một hàm twoSum (), nhận vào một mảng và tổng mục tiêu và lấy thời gian và không gian tuyến tính để trả về các chỉ số của hai số cộng lại tổng mục tiêu nếu không là -1.

Sau đó, chúng tôi viết hàm thực tế ThreeSum (), lặp lại từng phần tử trong mảng để tìm chỉ số của phần tử thứ ba mà khi được thêm vào hai sốSum () có thể thêm vào mục tiêu thực.

Do đó, như vậy, chúng ta có thể tìm thấy ba phần tử trong thời gian O (N ^ 2). Hãy viết mã cho việc này -

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

Đầu ra

Đầu ra trong bảng điều khiển sẽ là -

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