Skip to content

Instantly share code, notes, and snippets.

@danielyaa5
Created February 19, 2020 17:33
Show Gist options
  • Save danielyaa5/21099416944f7581b61b075418d11e41 to your computer and use it in GitHub Desktop.
Save danielyaa5/21099416944f7581b61b075418d11e41 to your computer and use it in GitHub Desktop.
// ==Question==
// Given a sequence of integers and an integer total target, return whether a contiguous sequence of integers sums up to target.
// ===Example===
// [1, 3, 1, 4, 23], 8 : True (because 3 + 1 + 4 = 8)
// [1, 3, 1, 4, 23], 7 : False
// total = 9
// [1, 3, 1, 4, 23], 8
// .^
// ^
// [1, 3, 1, 4, 23], 8
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 0, total = 0)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 1, total = 1)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 2, total = 4)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 3, total = 5)
// solution([1, 3, 1, 4, 23], 8, n = 5, left = 0, right = 4, total = 9) // returns true
// total = 4
// [3, -1, 1, 1, 4, 23], 48
// ^
// ^
// total = 4
// target = 5
// [3, -1, 1, 1, 4, 23], 48
const solution = (arr, target, n = arr.length, left = 0, right = 0, total = 0) => {
if (!arr || arr.length === 0) return false;
if (target === 0) return true;
if (right > n || left > n) return false;
if (total === target) return true;
if (total < target) return solution(arr, target, n, left, right + 1, total + arr[right]);
return solution(arr, target, n, left + 1, right, total - arr[left]);
};
const solution2 = (arr, target) => {
const cumSumMap = new Map();
let sum = 0;
return arr.some(val => {
sum += val;
cumSumMap.set(sum, true);
return (val === target || cumSumMap.has(target - val));
});
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment