Facebook Interview Question Interns
Country: United States
Interview Type: In-Person
That's a java linear-time constant space solution. Starts from an interval that contains only the first elements, then grows it to the right when its sum is too small and shrinks it on the left when its sum is too large.
@Anonymous, no, this solution is correct.
Since all numbers are positive, array of partial sums is strictly increasing.
Now you are given an array of strictly increasing elements and have to answer in linear time if there are two elements that aj - ai = delta, j > i
So the dumb approach would be to binary search for j for every index i.
Then we see that if we increase i, the second index j will only increase, it can't decrease. So we just move j until aj - ai < delta (if aj - ai = delta, we've found the solution) and then do i = i + 1 after that.
This solution doesn't take into account targets of values that are already included in the array. They will return false each time, which isn't a correct solution.
O(n) solution
class Solution {
public static boolean containsSubarray(int[] numbers, int target){
//input numbers is all positive
if(target < 0) return false;
if(target == 0) return true;
int startIndex = 0;
int runningSum = 0;
for(int i = 0; i < numbers.length; i++){
runningSum += numbers[i];
while(runningSum > target && startIndex < i){
runningSum -= numbers[startIndex];
startIndex ++;
}
if(runningSum == target){
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] numbers = new int[]{1, 1, 3, 5, 7, 9};
int target = 8;
System.out.println( containsSubarray(numbers, target) );
}
}
Java code
private static boolean addEls(int n, int[] els) {
// key will be sum
// array list will be the integers that have been added together
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < els.length; i ++) {
for (int j = 1; j < els.length-1; j++) {
Integer sum = new Integer(i+j);
ArrayList<Integer> sumFactors = hm.get(sum);
if (sumFactors == null)
sumFactors = new ArrayList<Integer>();
sumFactors.add(new Integer(i));
sumFactors.add(new Integer(j));
hm.put(sum, sumFactors);
}
}
return (hm.containsKey(n));
}
private static boolean addEls(int n, int[] els) {
// key will be sum
// array list will be the integers that have been added together
HashMap<Integer, ArrayList<Integer>> hm = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < els.length; i ++) {
for (int j = 1; j < els.length-1; j++) {
Integer sum = new Integer(i+j);
ArrayList<Integer> sumFactors = hm.get(sum);
if (sumFactors == null)
sumFactors = new ArrayList<Integer>();
sumFactors.add(new Integer(i));
sumFactors.add(new Integer(j));
hm.put(sum, sumFactors);
}
}
return (hm.containsKey(n));
}
static boolean doesSumToTarget(int arr[], int target) {
if (arr[0] == target) return true;
if (arr.length < 2) return false;
int left = 0, right = 1, sum = arr[0];
while (right < arr.length + 1) {
if (sum < target) {
if (right < arr.length)
sum += arr[right++];
}
else if (sum > target) {
sum -= arr[left++];
if (left == right && right < arr.length)
sum += arr[right++];
}
else {
System.out.print("{ ");
for (int i = left; i < right; i++)
System.out.print(String.valueOf(arr[i]) + " ");
System.out.println("}");
return true;
}
}
return false;
}
input:
int[] arr = {1, 2, 3, 4, 5};
System.out.println(doesSumToTarget(arr, 7));
output:
{ 3 4 }
true
for (i = 0;i< SIZE;i++)
S[i] = s[i] + a[i]
for (i=0;i<size-1;i++)
for (j=i;j<size;j++)
if (s[i] - s[j]) == target
print i, j
This will give you a time complexity of O(n^2), which is undesired. Try to do better than that.
public static ArrayList sum_target(int arr[],int target)
{
ArrayList<Integer> res=new ArrayList<>();
int sum=0;
if(arr.length<=1)
return res;
int i=0,j=arr.length;
for(i=0;i<arr.length;i++)
{
j=i;
sum=0;
while(sum<target)
{
sum+=arr[j++];
}
//System.out.println(sum);
if(sum==target)
{
break;
}
}
for(int k=i;k<j;k++)
res.add(arr[k]);
return res;
}
c++, implementation, O(n^2)
typedef long long INT64;
bool consecutiveSubSum(vector<int>& arr, int target) {
vector<INT64> subsum;
int i, j;
subsum.assign(arr.size() + 1, 0);
for (i = 0; i < arr.size(); i++) {
subsum[i + 1] = subsum[i] + arr[i];
}
for (i = 0; i < subsum.size(); i++) {
for (j = 0; j < i; j++) {
if (subsum[i] - subsum[j] == target) return true;
}
}
return false;
}
{
public static boolean isTargetNumberPossible(int aTargetNumber, int[] array) {
int count = 0;
int temp = 0;
boolean startIndexFlag = true;
int startIndex = -1;
while (count < array.length) {
if (temp == aTargetNumber) {
System.out.println("Sum is possible");
return true;
} else if (temp < aTargetNumber) {
temp = temp + array[count];
if (startIndexFlag) {
startIndex = count;
startIndexFlag = false;
}
count++;
} else {
count = startIndex + 1;
temp = temp - array[startIndex];
startIndexFlag = true;
startIndex = count;
}
}
return false;
}
}
public static boolean isTargetNumberPossible(int aTargetNumber, int[] array) {
int count = 0;
int temp = 0;
boolean startIndexFlag = true;
int startIndex = -1;
while (count < array.length) {
if (temp == aTargetNumber) {
System.out.println("Sum is possible");
return true;
} else if (temp < aTargetNumber) {
temp = temp + array[count];
if (startIndexFlag) {
startIndex = count;
startIndexFlag = false;
}
count++;
} else {
count = startIndex + 1;
temp = temp - array[startIndex];
startIndexFlag = true;
startIndex = count;
}
}
return false;
}
public static boolean isTargetNumberPossible(int aTargetNumber, int[] array) {
int count = 0;
int temp = 0;
boolean startIndexFlag = true;
int startIndex = -1;
while (count < array.length) {
if (temp == aTargetNumber) {
System.out.println("Sum is possible");
return true;
} else if (temp < aTargetNumber) {
temp = temp + array[count];
if (startIndexFlag) {
startIndex = count;
startIndexFlag = false;
}
count++;
} else {
count = startIndex + 1;
temp = temp - array[startIndex];
startIndexFlag = true;
startIndex = count;
}
}
return false;
}
Linear time (O(n)) solution.
class Solution {
public static boolean containsSubarray(int[] numbers, int target){
//input numbers is all positive
if(target < 0) return false;
if(target == 0) return true;
int startIndex = 0;
int runningSum = 0;
for(int i = 0; i < numbers.length; i++){
runningSum += numbers[i];
while(runningSum > target && startIndex < i){
runningSum -= numbers[startIndex];
startIndex ++;
}
if(runningSum == target){
return true;
}
}
return false;
}
public static void main(String[] args) {
int[] numbers = new int[]{1, 1, 3, 5, 7, 9};
int target = 8;
System.out.println( containsSubarray(numbers, target) );
}
}
void targetNo(int iArr[SIZE],int iTarget)
{
int sum =0;
for(int j=0,i=0;i<SIZE;i++)
{
if(sum < iTarget)
{
sum = sum + iArr[i];
if(sum > iTarget && i==SIZE-1)
{
sum = iArr[i] + iArr[i-1];
j=i-1;
}
}
else
{
j=j+1;
sum =iArr[j];
i=j;
continue;
}
if(sum == iTarget)
{
cout << endl;
for(int k =j;k<=i;k++)
cout << iArr[k] << " ";
break;
}
}
}
@kyduke, I as well started with subsums, but then instead of doing N^2 comparisons treated this as 2SUM problem, where a-b=TargetSum and 'a' and 'b' are from the subsums array.
public class SubArrayWithSum {
public boolean hasSubArrayWithSum(int[] input, int sum) {
return getSubArrayWithSum(input, sum) != null;
}
public int[] getSubArrayWithSum(int[] input, int sum) {
int[] subSumArr = getSubSums(input);
Map<Integer, Integer> pairsMap = new HashMap<>();
for (int i =0; i<subSumArr.length; i++) {
if (pairsMap.containsKey(Integer.valueOf(subSumArr[i]))) {
return subArray(input, pairsMap.get(subSumArr[i]), i-1);
} else {
pairsMap.put(sum + subSumArr[i], Integer.valueOf(i));
}
}
return null;
}
private int[] subArray(int[] input, int start, int end) {
int[] subArr = new int[end-start+1];
for(int i = 0; i<subArr.length; i++) {
subArr[i] = input[i+start];
}
return subArr;
}
private int[] getSubSums(int[] input) {
int[] subSums = new int[input.length+1];
subSums[0] = 0;
for (int i = 1; i<=input.length; i++) {
subSums[i] = subSums[i-1] + input[i-1];
}
return subSums;
}
}
C++ implementation using recursion.
using namespace std;
#include <iostream>
#include <vector>
bool addUpToTarget(vector<int> & array, int target, int startIndex, int endIndex) {
for(int i= startIndex; i <= endIndex; ++i) {
if(target == array[i]) {
return true;
} else if(target > array[i]) {
int newTarget = target - array[i];
if(addUpToTarget(array, newTarget, i+1, endIndex)) {
return true;
}
}
}
return false;
}
def cons_sum(numbers, sum):
start_idx = 0
end_idx = 0
calc_sum = numbers[0]
while start_idx <= end_idx and end_idx < len(numbers):
if calc_sum == sum:
return numbers[start_idx:end_idx+1]
elif calc_sum < sum:
end_idx += 1
if end_idx < len(numbers):
calc_sum += numbers[end_idx]
else:
calc_sum -= numbers[start_idx]
start_idx += 1
if end_idx < start_idx:
end_idx = start_idx
return []
Saw a similar solution but wanted to post, The idea is to use two index and the sum of the values between them, the values are add/subtracted according to the target value, at the same time a list with this values is updated
public List<int> FindSubList(int[] values, int target)
{
List<int> result = new List<int>();
if (values == null || values.Length == 0)
return result;
int start = 0;
int end = 0;
int sum = values[0];
result.Add(sum);
while (end < values.Length)
{
if (sum == target)
return result;
if (sum < target)
{
end++;
if (end < values.Length)
{
sum += values[end];
result.Add(values[end]);
}
}
else
{
sum -= values[start];
start++;
result.RemoveAt(0);
}
}
result.Clear();
return result;
}
Javascript:
function hasSum(arr, target){
if (arr.length == 1){
if (arr[0] == target) return true;
else return false;
}
for (var i=1; i<arr.length; i++){
var sum = 0;
var trace = [];
for (var j=0; j<=i; j++){
sum += arr[j];
if (sum == target) return true;
}
}
arr.shift();
return hasSum(arr, target);
}
function hasSum(arr, target){
if (arr.length == 1){
if (arr[0] == target) return true;
else return false;
}
for (var i=1; i<arr.length; i++){
var sum = 0;
var trace = [];
for (var j=0; j<=i; j++){
sum += arr[j];
if (sum == target) return true;
}
}
arr.shift();
return hasSum(arr, target);
}
public static void consecutivesum()
{
int[] ele = {1,3,5,7,9};
int target = 16;
int beginIdx= 0;
int endIdx = 1;
int tempSum = ele[beginIdx];
while(beginIdx <= endIdx && endIdx < ele.length)
{
if(tempSum == target)
{
System.out.print("{");
for(int i = beginIdx;i < endIdx;i++)
{
System.out.print(""+i);
}
System.out.print("}");
return;
}
if(tempSum < target)
{
tempSum += ele[endIdx];
endIdx++;
}
else{
tempSum -= ele[beginIdx];
beginIdx++;
}
}
}
public static void consecutivesum()
{
int[] ele = {1,3,5,7,9};
int target = 15;
int beginIdx= 0;
int endIdx = 1;
int tempSum = ele[beginIdx];
while(beginIdx <= endIdx && endIdx < ele.length)
{
if(tempSum == target)
{
System.out.print("{");
for(int i = beginIdx;i < endIdx;i++)
{
System.out.print(""+ele[i]);
}
System.out.print("}");
return;
}
if(tempSum < target)
{
tempSum += ele[endIdx];
endIdx++;
}
else{
tempSum -= ele[beginIdx];
beginIdx++;
}
}
System.out.println("No solution\n");
}
void findSegment(int *arr, int n, int target){
// closest is the closest position on the left such that sum from closest to current position
// is greater or equal target
int closest = -1; //doesn't exist initially
int* sum = new int[n];
int* res = NULL;
for (int i = 0; i < n; i++){
//sum[i]: sum of the first i+1 elements
if (i == 0) sum[i] = arr[i]; else sum[i] = sum[i-1] + arr[i];
if (sum[i] < target) continue;
// find new closest
if (closest == -1)
if (sum[i] >= target) closest = 0;
while (closest <= i && sum[i] - sum[closest] + arr[closest] >= target){
closest++;
}
closest--;
if (sum[i] - sum[closest] + arr[closest] == target) {
for (int j = 0; j < i - closest + 1; j++)
cout << arr[closest + j] << " " ;
return;
}
}
cout << "No solution !" << endl;
}
}
void findSegment(int *arr, int n, int target){
// closest is the closest position on the left such that sum from closest to current position
// is greater or equal target
int closest = -1; //doesn't exist initially
int* sum = new int[n];
int* res = NULL;
for (int i = 0; i < n; i++){
//sum[i]: sum of the first i+1 elements
if (i == 0) sum[i] = arr[i]; else sum[i] = sum[i-1] + arr[i];
if (sum[i] < target) continue;
// find new closest
if (closest == -1)
if (sum[i] >= target) closest = 0;
while (closest <= i && sum[i] - sum[closest] + arr[closest] >= target){
closest++;
}
closest--;
if (sum[i] - sum[closest] + arr[closest] == target) {
for (int j = 0; j < i - closest + 1; j++)
cout << arr[closest + j] << " " ;
return;
}
}
cout << "No solution !" << endl;
}
void findSegment(int *arr, int n, int target){
// closest is the closest position on the left such that sum from closest to current position
// is greater or equal target
int closest = -1; //doesn't exist initially
int* sum = new int[n];
int* res = NULL;
for (int i = 0; i < n; i++){
//sum[i]: sum of the first i+1 elements
if (i == 0) sum[i] = arr[i]; else sum[i] = sum[i-1] + arr[i];
if (sum[i] < target) continue;
// find new closest
if (closest == -1)
if (sum[i] >= target) closest = 0;
while (closest <= i && sum[i] - sum[closest] + arr[closest] >= target){
closest++;
}
closest--;
if (sum[i] - sum[closest] + arr[closest] == target) {
for (int j = 0; j < i - closest + 1; j++)
cout << arr[closest + j] << " " ;
return;
}
}
cout << "No solution !" << endl;
}
void findSegment(int *arr, int n, int target){
// closest is the closest position on the left such that sum from closest to current position
// is greater or equal target
int closest = -1; //doesn't exist initially
int* sum = new int[n];
int* res = NULL;
for (int i = 0; i < n; i++){
//sum[i]: sum of the first i+1 elements
if (i == 0) sum[i] = arr[i]; else sum[i] = sum[i-1] + arr[i];
if (sum[i] < target) continue;
// find new closest
if (closest == -1)
if (sum[i] >= target) closest = 0;
while (closest <= i && sum[i] - sum[closest] + arr[closest] >= target){
closest++;
}
closest--;
if (sum[i] - sum[closest] + arr[closest] == target) {
for (int j = 0; j < i - closest + 1; j++)
cout << arr[closest + j] << " " ;
return;
}
}
cout << "No solution !" << endl;
}
Swift solution:
func sumConsecutiveNumbers(numberArray: [Int], target: Int) -> Bool {
if numberArray.count == 0 {
return false
}
var start = 0
var end = 0
var sum = 0
while end < numberArray.count {
if sum > target {
sum -= numberArray[start++]
}
else {
sum += numberArray[end++]
}
if sum == target {
return true
}
}
return false
}
groovy
static boolean existConsecutiveElementsAddUpToTarget(List<Integer> integers, int target) {
int i = 0
while (i < integers.size() - 1) {
int first = integers.get(i)
int second = integers.get(i+1)
if (first != 0 && second != 0 && first + second == target) {
println "true {${[first, second]}}"
return true
}
i++
}
println "false"
return false
}
#include<iostream>
bool subArray(int A[], int sumValue, int n, int * sI, int *eI)
{
int i=0;
*sI=0;
int sum= A[0];
while (i< n)
{
if (sum == sumValue)
{
*eI= i;
return true;
}
else if (sum > sumValue)
{
sum= sum - A[*sI];
(*sI)++;
}
else
{
i++;
sum= sum + A[i];
}
}
return false;
}
int main()
{
int A[]= {2, 3, 1, 5, 4, 6, 7};
int len= sizeof(A)/sizeof(int);
int sI, eI;
if (subArray(A, 28, len, &sI, &eI))
{
for(int i=sI; i<=eI; i++)
printf("%d value\n", A[i]);
}
else
printf("Not fund such subArray\n");
}
public static boolean solution(int[] nums, int target) {
if (nums.length == 0) {
System.out.println("false");
return false;
}
int start = 0;
int sum = 0;
int end = 0;
for (; end < nums.length; end += 1) {
sum += nums[end];
while (sum > target) {
sum -= nums[start];
start += 1;
}
if (sum == target) {
System.out.println("true");
return true;
}
}
System.out.println("false");
return false;
}
public static boolean solution(int[] nums, int target) {
if (nums.length == 0) {
System.out.println("false");
return false;
}
int start = 0;
int sum = 0;
int end = 0;
for (; end < nums.length; end += 1) {
sum += nums[end];
while (sum > target) {
sum -= nums[start];
start += 1;
}
if (sum == target) {
System.out.println("true");
return true;
}
}
System.out.println("false");
return false;
}
public static boolean solution(int[] nums, int target) {
if (nums.length == 0) {
System.out.println("false");
return false;
}
int start = 0;
int sum = 0;
int end = 0;
for (; end < nums.length; end += 1) {
sum += nums[end];
while (sum > target) {
sum -= nums[start];
start += 1;
}
if (sum == target) {
System.out.println("true");
return true;
}
}
System.out.println("false");
return false;
}
public bool FindConsequitve(int[] values, int target)
{
int sum = values[0];
int begin = 0;
int end = 0;
while (end < values.Length)
{
if (sum == target)
return true;
if (begin == end && values[begin] > target)
{
begin++;
end++;
sum = values[begin];
}
else if (sum < target)
{
end++;
if (end < values.Length)
sum += values[end];
}
else
{
sum -= values[begin];
begin++;
}
}
return false;
}
Linear Solution : Time Complexity o(n); No Additional Space required.
public static int[] getTargetArray(int[] input, int target) {
int startPos = 0;
int endPos = 0;
int length = input.length;
int sum = 0;
boolean subArrayFound = false;
for (int i = 0; i < length; i++) {
sum += input[i]; // 9
if (sum > target) {
while(sum > target) {
sum -= input[startPos++];
if (sum < 0)
sum = 0;
}
}
if (sum == target) {
endPos = i;
subArrayFound = true;
break;
}
}
if (!subArrayFound)
return null;
int[] subArray = new int[endPos - startPos + 1];
for (int k = 0; k < subArray.length; k++) {
subArray[k] = input[k+startPos];
}
return subArray;
}
bool check_consequtive_sum(int a[], int target, int len)
{
int sum = target;
int pos, start;
pos=start = 0;
while (start<len)
{
if (sum==0)
{
return true;
}
else if(sum>0)
{
sum-=a[start++];
}
else if (sum<0)
{
sum = target;
pos++;
start = pos;
}
}
return false;
}
int main()
{
int a[] = {1,3,5,7,9};
int target[] = {8,15,6};
int len1 = sizeof(a)/sizeof(*a);
int len = sizeof(target)/sizeof(*target)-1;
while(len>=0){
if (check_consequtive_sum(a,target[len--],len1)){
cout<<"true"<<"\n";
} else {
cout<<"false"<<"\n";
}
}
return 0;
}
bool check_consequtive_sum(int a[], int target, int len)
{
int sum = target;
int pos, start;
pos=start = 0;
while (start<len)
{
if (sum==0)
{
return true;
}
else if(sum>0)
{
sum-=a[start++];
}
else if (sum<0)
{
sum = target;
pos++;
start = pos;
}
}
return false;
}
int main()
{
int a[] = {1,3,5,1,7,9};
int target[] = {8,15,6};
int len1 = sizeof(a)/sizeof(*a);
int len = sizeof(target)/sizeof(*target)-1;
while(len>=0){
if (check_consequtive_sum(a,target[len--],len1)){
cout<<"true"<<"\n";
} else {
cout<<"false"<<"\n";
}
}
return 0;
}
bool check_consequtive_sum(int a[], int target, int len)
{
int sum = target;
int pos, start;
pos=start = 0;
while (start<len)
{
if (sum==0)
{
return true;
}
else if(sum>0)
{
sum-=a[start++];
}
else if (sum<0)
{
sum = target;
pos++;
start = pos;
}
}
return false;
}
int main()
{
int a[] = {1,3,5,1,7,9};
int target[] = {8,15,6};
int len1 = sizeof(a)/sizeof(*a);
int len = sizeof(target)/sizeof(*target)-1;
while(len>=0){
if (check_consequtive_sum(a,target[len--],len1)){
cout<<"true"<<"\n";
} else {
cout<<"false"<<"\n";
}
}
return 0;
}
public class example {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={1,2,3,4,5};
int target = 5;
boolean c = findTarget(a, target);
System.out.println(c);
}
private static boolean findTarget(int[] b, int target) {
// TODO Auto-generated method stub
for(int i=0;i<b.length-1;i++)
{
if(b[i]+b[i+1] == target)
return true;
}
return false;
}
}
public class example {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={1,2,3,4,5};
int target = 5;
boolean c = findTarget(a, target);
System.out.println(c);
}
private static boolean findTarget(int[] b, int target) {
// TODO Auto-generated method stub
for(int i=0;i<b.length-1;i++)
{
if(b[i]+b[i+1] == target)
return true;
}
return false;
}
}
import java.util.*;
/* Given positive int array, determine whether there is a set of consecutive ints that add up to target */
public class ConsecutiveSum {
public static int[] arr = {1,3,5,7,9};
public static int target = 6;
public static Vector<Integer> findSet(int[] arr, int target){
int i, j, sum = 0;
int length = arr.length;
Vector<Integer> ret = new Vector <Integer>(1);
for(i = 0; i < length; i++){
sum += arr[i];
for (j = i + 1; j < length; j++){
if(sum + arr[j] == target){
//found
if(ret.indexOf(arr[i]) < 0){
ret.add(arr[i]);
}
ret.add(arr[j]);
return ret;
} else if(sum + arr[j] < target){
sum += arr[j];
if(ret.indexOf(arr[i]) < 0){
ret.add(arr[i]);
}
ret.add(arr[j]);
} else break;
}
sum = 0;
ret.removeAllElements();
ret.setSize(1);
}
return ret;
}
public static void main (String[] args){
Vector<Integer> result = new Vector<Integer>();
result = findSet(arr, target);
if(result.size() < 2){
System.out.println("False");
} else{
System.out.println("True");
for(int i = 1; i < result.size(); i++){
System.out.print(result.get(i) + " ");
}
System.out.println("\n");
}
}
}
My Javascript solution:
function getConsecutivesThatSum(numbers, target) {
var i;
var j;
var sum;
for (i = 0; i < numbers.length; i++) {
sum = numbers[i];
for (j = i+1; j < numbers.length; j++) {
sum += numbers[j];
if (sum > target) {
break;
} else if (sum < target) {
continue;
} else {
return { success: true, result: numbers.slice(i, j + 1)};
}
}
}
return { success: false };
}
getConsecutivesThatSum([1,3,5,7,9], 8);
// { success: true, result: [3,5] }
getConsecutivesThatSum([1,2,3,4,5], 7);
// { success: true, result: [3,4]}
getConsecutivesThatSum([1,3,5,7,9], 15);
// { success: true, result: [3,5,7]}
getConsecutivesThatSum([1,3,5,7,9], 6);
// { success: false}
getConsecutivesThatSum([6], 6);
// { success: false}
/*
dynamic programming approach. Creates a O(n^2) space to store partial
sums which are useful in printing the path.
for an input {1,5,3,7,9}, sum is a sparse matrix when fully populated:
1
6 5
9 8 3
16 15 10 7
25 24 19 16 9
Since the getSum() is called only when either decrementing i or j, and uses
a memoized sum matrix, the complexity of algorithm is O(n + n) = O(n)
*/
static void sumTarget(int[] array, int target){
int length = array.length;
int[][] sum = new int[length][length];
for(int i = 0 ; i < length; i++){
sum[i][i] = array[i];
}
boolean found = false;
int i = length-1;
int j = length-1;
int value = 0;
while(true){
value = getSum(array, sum, i, j);
if(target == value){
found = true;
break;
}
if(i-1 < 0 || j-1 < 0){
found = false;
break;
}
if(target < value){
// can't go straight up the array, so go diagonally up
if (i == j)
j--;
i--;
}else{
// go left
j--;
}
}
if (!found) {
System.out.println(target + "= false");
} else {
System.out.print(target + "= true: {");
for (; j < i; j++)
System.out.print(array[j] + ",");
System.out.println(array[j] + "}");
}
}
static int getSum(int[] array, int[][] sum, int i, int j){
if(i < 0 || j < 0){
return 0;
}
if(sum[i][j] == 0){
sum[i][j] = getSum(array, sum,i-1,j) + array[i];
}
return sum[i][j];
}
sum = 0
res_array=list()
def findsum(item, arr):
i=0
for i in range(len(arr) - 1):
sum = arr[i]
for j in range(1,len(arr)- i):
sum = sum + arr[i+j]
if sum == item:
for x in range(i,i+j+1):
res_array.append(arr[x])
return res_array
if __name__=="__main__":
arr = [1,3,3,1,9,3,5]
item = 8
res_array=findsum(item,arr)
print res_array
- Irit October 28, 2015public static boolean solution(int[] nums, int target) { if(nums.length == 0) { return target == 0; } int start = 0; int end = 0; int sum = nums[0]; if (sum == target) { return true; } while(end < nums.length) { if(sum > target) { sum -= nums[start]; start++; } else { end++; if(end < nums.length) { sum += nums[end]; } } if (sum == target) { return true; } } return false; }