Did you coded a solution < O(n^2 + logn) ?

Assuming each number only appears once: //Java code public static void targetsum(int[] arr, int target) { if(arr == null) return; int start = 0; int end = arr.length -1; while(start target end--; } }

typedef vector vint; bool check_element_sum(vint &array) { // n^2 algorithm sort(array.begin(),array.end()); //general case : nlogn copy(array.begin(),array.end(),ostream_iterator(cout," ")); cout=0;--i) //n^2 { start=0; end=i-1; target=array[i]; //note a<=b<=c for the tuples formed here hence check for c=a+b only while(start

we can modify the 3sum algorithm for this.

It is possible to do it in O(n) create a binary tree from the sorted array in O(n) subtract each value in array from target and find if its there in the tree, if found push to hash map, with the array item as key and the subtracted value as key next time before subtracting value in the array from target check if it is in the hash map

@Pal the hash map gives a lower constan because /2 elements need to be checked but the lookup is still n*logn

import java.util.Arrays; import java.util.HashSet; import java.util.List; import java.util.Random; import java.util.Scanner; import java.util.Set; public class SumOfTwoElements { public static void main(String[] args) { final Scanner in = new Scanner(System.in); final Random random = new Random(); while (true) { System.out.println("Enter array size : "); int size = in.nextInt(); int[] array = new int[size]; for (int i = 0; i > findSummingTriplets2(int[] array) { final Set> summingTriplets = new HashSet>(); for (int k = 2; k array[k]) { j--; } else if (sum > findSummingTriplets(int[] array) { final Set> summingTriplets = new HashSet>(); for (int i = 0; i end) { return false; } int mid = start + (end - start) / 2; if (array[mid] > value) { return contains(array, start, mid - 1, value); } else if (array[mid] < value) { return contains(array, mid + 1, end, value); } else { return true; } } }

bool sumExists(vector nums, int target) { auto front = nums.begin(); auto back = nums.end() - 1; while (front != back) { if (*front + *back == target) return true; else if (*front + *back < target) front++; else back--; } return false; }