LeetCode: Bài Toán Two Sum II - Input Array Is Sorted

Bài toán: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Giải pháp

Sử dụng 2 pointer tương ứng với index đầu và cuối ($left và $right) của mảng $numbers.

Nếu tổng giá trị tại 2 pointer bằng $target => Trả về kết quả.

Nếu tổng giá trị lớn hơn $target => giảm pointer $right về 1

Nếu tổng giá trị nhỏ hơn $target => cộng pointer $left về 1

Time Complexity: O(n)

Space Complexity: O(1)

class Solution {

    /**
     * @param Integer[] $numbers
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($numbers, $target) {
        $left = 0;
        $right = count($numbers) - 1;

        while ($left < $right) {
            $sum = $numbers[$left] + $numbers[$right];

            if ($sum == $target) {
                return [$left + 1, $right + 1];
            } if ($sum > $target) {
                $right--;
            } else {
                $left++;
            }
        }
    }
}