Skip to content

Instantly share code, notes, and snippets.

@rodcisal
Created May 2, 2021 09:29
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save rodcisal/6195f29591a7e56cf4e983c05d551e6a to your computer and use it in GitHub Desktop.
Get Pairs that makes target number
function getPairs (array: number[], target: number): number {
const needed = {};
let result = 0;
for (let i = 0; i < array.length; i++) {
// store pair that makes target with element from original array and index
needed[array[i] - target] = i;
}
for (let i = 0; i < array.length; i++) {
// check that pair that makes target exists and it's not same element in original array
if (needed[array[i]] !== undefined && needed[array[i]] !== i) {
result++
// element used in pair so deleted from needed array
needed[array[i]] = undefined;
}
}
return result;
}
// Time complexity is O(N+N) which means O(N)
// https://stackoverflow.com/questions/5872120/time-complexity-of-two-for-loops
test('passing array [1, 2, 3, 4] with target 1', () => {
const r = getPairs([1,2,3,4], 1);
expect(r).toBe(3);
});
test('passing array [-2, 2, 0, 4] with target 2', () => {
const r = getPairs([-2, 2, 0, 4], 2);
expect(r).toBe(3);
});
test('passing array [-2, 2, 2, 0, 4] with target 2', () => {
const r = getPairs([-2, 2, 2, 0, 4], 2);
expect(r).toBe(3);
});
test('passing array [2, 4, 6, 8] with target 2', () => {
const r = getPairs([2, 4, 6, 8], 2);
expect(r).toBe(3);
});
test('passing array [8, 5, 3, 0] with target 3', () => {
const r = getPairs([8, 5, 3, 0], 3);
expect(r).toBe(2);
});
test('with empty array', () => {
const r = getPairs([], 10);
expect(r).toBe(0);
});
test('passing array [-2,2] with target 0', () => {
const r = getPairs([-2,2],0);
expect(r).toBe(0);
});
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment