Description
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.
Tests
Let’s start out with the tests:
procedure AssertTwoSum(Input: Array, Target, First, Second: Integer);
begin
var Result := TwoSum(Input, Target);
AssertEqual (0, Result[0]);
AssertEqual (1, Result[1]);
end
test '2 7 11 5';
begin
AssertTwoSum ([2, 7, 11, 15], Target: 9, First: 0, Second: 1);
end
test '3 2 4';
begin
AssertTwoSum ([3, 2, 4], Target: 6, First: 1, Second: 2);
end
test '3 3';
begin
AssertTwoSum ([3, 3], Target: 6, First: 0, Second: 1);
end
Solution
For each item in the array of integers, loop through the array, comparing if the both values add up to the target, making sure the indexes are not the same.
function TwoSum(Input: Array of Integer, Target: Integer) : Array of Integer;
begin
for var I := 0; I < Input.Length; I := I + 1 do
begin
for var J := 0; J < Input.Length; J := J + 1 do
begin
if Input[I] + Input[J] = Target And I <> J then
begin
Exit [I, J];
end
end
end
raise 'Invalid Input!';
end
This is the simplest way to solve the problem, but not the most time efficient. It has a time complexity of O(n2). The time can be reduced by initializing the J loop variable with I, since, if you think about it, these permutations have already been covered.
Let’s run the tests:
Alternate Solution
With a solution in place, and all our tests passing, now we can think of performance. By adding a hash table lookup we can reduce the time complexity to O(n) at the cost of the extra memory that the hash table takes up.
function TwoSum(Input: Array of Integer, Target: Integer) : Array of Integer;
var
Lookup : Map := Map();
begin
for var I := 0; I < Input.Length; I := I + 1 do
begin
var Value := Input[I];
var Complement := Target - Value;
if Lookup.Contains(Complement) then
begin
Exit [Lookup.Get(Complement), I];
end
Lookup.Put(Value, I);
end
raise 'Invalid Input!';
end
Of course, the performance is going to depend on the implementation of the hash table, but for a properly written hash table the lookup should be in constant time regardless of how many keys are in the table.
Replace the implementation, and run the tests again!
Leave a Reply