CareerCup

algo: O(n^2):
Fill 2 2d arrays with
arr1[i][j]=a[i]+a[j]
arr2[i][j]=a[j]-a[i]
j>i
In a map<int,list<int>>, map[arr1[i][j]].push_back(j)
For each element in arr2, search in the map.
Count all hits where j < k

we can use 1d arrays:

unsigned count_tuples(vector<int>& numbers){
	unordered_map<int, unsigned> sum2;
	unordered_map<int, unsigned> sum3;

	unsigned result = 0;
	for(unsigned i = 0; i < numbers.size(); ++i){
	    auto sum3it = sum3.find(numbers[i]);
		if(sum3it != sum3.end()){
			result += sum3it->second;
		}	

		for(const auto& sum : sum2){
			auto newSum = sum.first +numbers[i];
			auto sum3it = sum3.find(newSum);
			if(sum3it == sum3.end()){
				sum3.insert(make_pair(newSum, sum.second));
			} else {
				sum3it->second += sum.second;
			}
		}

		for(unsigned y = 0; y < i; ++y){
			auto newSum = numbers[y] +numbers[i];
			auto sum2it = sum2.find(newSum);
			if(sum2it == sum2.end()){
				sum2.insert(make_pair(newSum, 1));
			} else {
				++sum2it->second;
			}
		}
	}
	return result;
}

we can use just two additional 1-d arrays to solve

unsigned count_tuples(vector<int>& numbers){
	unordered_map<int, unsigned> sum2;
	unordered_map<int, unsigned> sum3;

	unsigned result = 0;
	for(unsigned i = 0; i < numbers.size(); ++i){
	    auto sum3it = sum3.find(numbers[i]);
		if(sum3it != sum3.end()){
			result += sum3it->second;
		}	

		for(const auto& sum : sum2){
			auto newSum = sum.first +numbers[i];
			auto sum3it = sum3.find(newSum);
			if(sum3it == sum3.end()){
				sum3.insert(make_pair(newSum, sum.second));
			} else {
				sum3it->second += sum.second;
			}
		}

		for(unsigned y = 0; y < i; ++y){
			auto newSum = numbers[y] +numbers[i];
			auto sum2it = sum2.find(newSum);
			if(sum2it == sum2.end()){
				sum2.insert(make_pair(newSum, 1));
			} else {
				++sum2it->second;
			}
		}
	}
	return result;
}

@jayz: your solution is not O(n^2) as you have to traverse to the list to count elements.

Python:

from collections import Counter

def num_of_summing_tuples(ar,n=4):
	num_of_matches = 0
	endings = Counter() #(result,numofops) -> count
	for value in reversed(ar):
		updater = Counter()
		updater.update({(-value,1) : 1})
		for k,count_so_far in endings.items():
			end_v , num_of_ops = k
			new_ending = value+end_v
			new_num_of_ops = num_of_ops + 1

			if new_ending==0 and new_num_of_ops==n:
				num_of_matches+=count_so_far

			if new_num_of_ops <= n-1:
				updater.update({(new_ending,new_num_of_ops) : count_so_far})

		endings.update(updater)
	return num_of_matches