LeetCode: Bài toán Two Sum

Bài toán: https://leetcode.com/problems/two-sum/description/

Giải pháp 1

Sử dụng 2 vòng lặp for để quét qua các phần tử trong mảng.

Cộng 2 giá trị nếu bằng $target thì trả về.

Độ phức tạp: O(n^2)

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $numCount = count($nums);
        for ($i = 0; $i < $numCount - 1; $i++) {
             for ($j = 1; $j < $numCount; $j++) {
                 if ($nums[$i] + $nums[$j] == $target) {
                     return [$i, $j];
                 }
             }
        }
}

Giải pháp 2: Tối ưu hơn.

Sử dụng 1 biến kiểu Map để giải quyết. Chi tiết trong code mình hoạ

Vì Map có độ phức tạp O(1) nên việc truy xuất phần tử là rất nhanh.

Độ phức tạp: O(n)

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $numCount = count($nums);
        $result = [];

        for ($i = 0; $i < $numCount; $i++) {
            $index = $target - $nums[$i];

            if (array_key_exists($index, $result)) {
                return [$result[$index], $i];
            } else {
                $result[$nums[$i]] = $i;
            }
        }
    }
}