Tìm số mong muốn trong mảng đã sắp xếp trong JavaScript

Chúng ta có một mảng số nguyên được sắp xếp theo thứ tự tăng dần. Chúng ta cần viết một hàm JavaScript nhận vào một mảng như vậy làm đối số đầu tiên và một số mục tiêu tổng làm đối số thứ hai.

Hàm nên tìm và trả về hai số từ mảng mà khi cộng lại cho tổng mục tiêu. Điều kiện giải bài toán này là phải làm trong thời gian tuyến tính và sử dụng không gian hằng số.

Ví dụ

Dưới đây là mã nguồn:

const arr = [4, 6, 8, 9, 11, 12, 18, 21]; const num = 27; const findElements = (arr = [], target) => {    let left = 0;    let right = arr.length - 1;    let res = [];    while (left < right) {       let leftElement = arr[left];       let rightElement = arr[right];       if (leftElement + rightElement === target) {          res.push(arr[left]);          res.push(arr[right]);          break;       } else if (leftElement + rightElement > target) {          right--;       } else {          left++;       }    }    return res; }; console.log(findElements(arr, num));

Kết quả

Đầu ra trên console:

[6, 21]

Giải thích: Two-pointer technique trên mảng sorted. Left từ đầu, right từ cuối. Tổng > target → right-- (giảm tổng). Tổng < target → left++ (tăng tổng). O(n) time, O(1) space. LeetCode 167 "Two Sum II - Input Array Is Sorted".