The triple sum problem

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

	A solution set is:
	[
	  [-1, 0, 1],
	  [-1, -1, 2]
	 ]

Here below compares two algorithms with time complexity and the experimental time compare:

• N^2 * logN number of 3sum 0 = 70 time spent = 0.029919s

  int tri_sum_better(int data[], int size) { int ret = 0;

  bubble_sort(data, size);
  
  for (int i = 0; i <= size - 1; ++i) {
    for (int j = i + 1; j <= size - 1; ++j) {
      int ij = data[i] + data[j];
      int res = binary_search(data, 0, size - 1, -ij);
      if (res != i && res != j && -1 != res) {
        ++ret;
      }
    }
  }
  
  return ret / 3;   }
  

• N^3 number of 3sum 0 = 70 time spent = 0.361940s

  int tri_sum_brute(int data[], int size) { int ret = 0; for (int i = 0; i < size; ++i) { for (int j = i + 1; j < size; ++j) { for (int k = j + 1; k < size; ++k) { if (0 == data[i] + data[j] + data[k]) { ++ret; } } } }

  return ret;   }
  

Source code on github:
Code.

07 Nov 2017