findSubArray.php

<?php

namespace App\Http\Controllers;

/**
 * Written in a Laravel controller for ease of development.
 * Nullable type hints (PHP 7.1 and up) in use.
 */
class TestController extends Controller
{
    /**
     * Test cases
     */
    public function index()
    {
        $one = $this->findSubArray([4, 8, 23, 57, 2, 4], 59);
        echo "<pre>";
        var_dump($one); //works: [3, 4]
        echo " </pre>";
        $two = $this->findSubArray([5, 6, 2, 4, 9, 1, 0], 9);
        echo "<pre>";
        var_dump($two); //works: [4, 4]
        echo " </pre>";
        $three = $this->findSubArray([1, 2, 3, 1, 2, 3, 4], 6);
        echo "<pre>";
        var_dump($three); //works: [0, 2]
        echo " </pre>";
        $four = $this->findSubArray([1, 2, 3, 1, 2, 3, 4], 100);
        echo "<pre>";
        var_dump($four); //works: null
        echo " </pre>";

        //Additional case for the "entire array equals sum" scenario
        $five = $this->findSubArray([4, 5, 6, 7, 8], 30);
        echo "<pre>";
        var_dump($five); //works: [0, 4]
        echo " </pre>";
    }

    /**
     * Given an unsorted array and a target number, return the start and end indexes of a continuous
     * set of elements within the array that sums to the given target number
     *
     * @param array $arr The array to test
     * @param int $target The sum to test for
     * @return array|null       Indices of the matching sub array whose sum equals $target.
     *                          Null if there are no matching sub-array
     */
    public function findSubArray(array $arr, int $target): ?array
    {
        //If a single array value matches the target, return the index as the start and end indices
        //for the return array
        if ($matchedIndex = array_search($target, $arr)) {
            return [$matchedIndex, $matchedIndex];
        }

        //Check if the entire array matches the sum, otherwise test permutations
        $match = array_sum($arr) === $target ? $arr : $this->generateAndTestPermutations($arr, $target);

        if (!$match) {
            return null;
        }

        //Use array_intersect_assoc in order to ensure that first sub-array that matches
        //is returned in case there are more than one. As this will return null if this indices do not match,
        //fall back to array_intersect
        $intersection = array_intersect_assoc($arr, $match);
        $keys = $intersection ? array_keys($intersection) :
            array_keys(array_intersect($arr, $match));

        //Return the first and last keys of the intersection
        return [$keys[0], $keys[count($keys) - 1]];
    }

    /**
     * Iterate through the indices of the array, generating permutations of the array starting at
     * consecutively larger indexes of all possible lengths.
     *
     * @param $arr      array       Array that's been validated to not already match the target sum
     * @param $target   int         The target sum: sub array sums will be checked against thi
     * @return array|null           A sub-array whose sum matches the target integer;
     *                              null if none found
     */
    private function generateAndTestPermutations(array $arr, int $target): ?array
    {
        $len = count($arr);
        $ret = null;
        for ($i = 0; $i < $len - 1; $i++) {
            //The outer loop generates smaller arrays slicing off the first item at each loop
            $arrayAtIndex = array_slice($arr, $i, $len);
            for ($j = 2; $j < $len; $j++) {
                //The inner loop generates a series progressively larger slices of $arrayAtIndex, beginning
                //with an array of length 2.
                $subArray = array_slice($arrayAtIndex, 0, $j);
                if (array_sum($subArray) === $target) {
                    $ret = $subArray;
                    break(2);
                }
            }
        }
        return $ret;
    }
}