3 Sum

Determine if there exists three elements in a given array that sum to the given target number. Return all the triple of values that sums to target.

Assumptions

• The given array is not null and has length of at least 3

• No duplicate triples should be returned, order of the values in the tuple does not matter

Examples

• A = {1, 2, 2, 3, 2, 4}, target = 8, return [[1, 3, 4], [2, 2, 4]]

Solution: left right pinch at every index

Iterate through array

only check for first appearance of each element

for each element check for (x + y = target - element)

If found:

1. add (element, x, y) to results

2. skip trailing duplicate x, continue searching

public class Solution {
  public List<List<Integer>> allTriples(int[] array, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(array);
    for (int i = 0; i < array.length - 2; i++){
      //ignore duplicates
      if (i > 0 && array[i] == array[i - 1]){
        continue;
      }

      int left = i + 1;
      int right = array.length - 1;
      while (left < right){
        int tmp = array[left] + array[right];
        if (tmp + array[i] == target){
          result.add(Arrays.asList(array[i], array[left], array[right]));
          left++;
          //ignore duplciate js
          while( left < right && array[left] == array[left - 1]){
            left++;
          }
        } else if (tmp + array[i] < target){
          left++;
        } else {
          right--;
        }
      }
    }
    return result;
  }
}

Time Comp: Two iterations O(N^2)

Space Comp: O(N) result storage