Skip to content

Instantly share code, notes, and snippets.

@sco-tt
Last active March 10, 2019 01:11
Show Gist options
  • Save sco-tt/3d80da7e70cc42f50335f48e4366712e to your computer and use it in GitHub Desktop.
Save sco-tt/3d80da7e70cc42f50335f48e4366712e to your computer and use it in GitHub Desktop.
<?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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment