This is my PHP algorithm for the twoSum problem in leetCode:
function twoSum($nums, $target) {
foreach($nums as $key1 => $num1) {
foreach(array_slice($nums, $key1 + 1, null, true) as $key2 => $num2) {
if ($num1 + $num2 === $target) {
return [$key1, $key2];
}
}
}
}
Its purpose is to take an array and check if the sum of two distinct elements can result in the $target
. Just like:
twoSum([2,7,11,15], 9);
// this sould return [0, 1] because 2 + 7 is 9
Initially I created an algorithm that compare the elements in $nums
through brute force. Knowing that O(N2) is not that good for time complexity, I tried to refactor it and came up with the solution above. I don't think that the code still with O(N2) time complexity, but I can't think how I could calculate this algorithm in Big O Notation, I would like to know if:
- Can you clearly explain what is the time complexity of this algorithm and why.
- The way this code works still is considered brute force.
Any other advice is very welcome!