Problem solve with PHP: Two sum

**Problem: **Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Here is leetcode problem, where all details are explain.

As far, I can solve the problem in three ways.

Solution 1

class Solution {

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

        for ( $i=0; $i<$n-1; $i++ ) {
            for ( $j=$i+1; $j<$n; $j++ ) {
                if ( $nums[$i] + $nums[$j] === $target ) {
                    return [$i, $j];
                }
            }
        }

}

Solution 2

class Solution {

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

        for ( $i = 0; $i < $n -1; $i++ ) {
            $remain = $target - $nums[$i];
            $arr_remain = array_slice( $nums, $i + 1 );

            if ( in_array( $remain, $arr_remain ) ) {
                $pos = array_search( $remain, $nums );
                if ( $pos === $i ) {
                    $arr_keys = array_keys( $nums, $remain );
                    $pos = $arr_keys[1];
                }
                return [ $i, $pos ];
            }
        }
    }
}

Solution 3

class Solution {

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

        $hash_table = [];
        for ( $i = 0; $i < $n - 1; $i++ ) {
            $remain = $target - $nums[$i];
            if ( in_array( $remain, $hash_table ) ) {
                $arr_key = array_keys( $hash_table, $remain );
                return [ $arr_key[0], $i ];
            }
            $hash_table[$i] = $nums[$i];
        }

    }
}

However, the 3rd solution should better optimized in algorithmic context, but I get the 1st solution is more fast. Any idea is most welcome for the reason of speed.

Comments

[Jake Doran]

I amended your solution 3 to something that worked:

function twoSum($nums, $target) {
        $n = count($nums);

        $hash_table = [];
        for ( $i = 0; $i < $n; $i++ ) {
            $remain = $target - $nums[$i];
            if ( in_array( $remain, $hash_table ) ) {
                $arr_key = array_keys( $hash_table, $remain );
                return [ $arr_key[0], $i ];
            }
            $hash_table[$i] = $nums[$i];
        }
}

I then amended the test case from [2,7,11,15] to be of an array size of 4000+ elements. Solution 1 completes somewhere between 250-500ms whereas the amended solution 3 completes somewhere between 20-55ms.

[Jake Doran]

Most likely due to the dataset in the the test cases being incredibly small as the array size is only 4.

Equally I cant get your solution 3 to work on leetcode 🤷