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.

Blog

Problem solve with PHP: Two sum

Mrinal Haque

Join Our Newsletter. No Spam, Only the good stuff.

Related