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: 为了去重，i只取duplicate第一个，k只取duplicate最后一个，j不用管

  public List<List<Integer>> allTriples(int[] array, int target) {
    Arrays.sort(array);
    List<List<Integer>> ans = new ArrayList<>();
    for (int k = array.length - 1; k >= 2; k--) {
      if (k + 1 < array.length && array[k] == array[k + 1]) {
        continue;
      }
      int i = 0, j = k - 1;
      while (i < j) {
        if (i > 0 && array[i] == array[i - 1]) {
          i++;
          continue;
        }
        int sum = array[i] + array[j] + array[k];
        if (sum == target) {
          List<Integer> pair = new ArrayList<>();
          pair.add(array[i]);
          pair.add(array[j]);
          pair.add(array[k]);
          ans.add(pair);
          i++;
          j--;
        } else if (sum < target) {
          i++;
        } else {
          j--;
        }
      }
    }
    return ans;
  }

4 sum: k sum, k - 1个指针负责去重

  public boolean exist(int[] array, int target) {
    Arrays.sort(array);
    for (int k = array.length - 1; k >= 3; k--) {
      if (k + 1 < array.length && array[k] == array[k + 1]) {
        continue;
      }
      for (int l = k - 1; l >=2; l--) {
        if (l + 1 < k && array[l] == array[l + 1]) {
          continue;
        }
        int i = 0, j = l - 1;
      while (i < j) {
        if (i > 0 && array[i] == array[i - 1]) {
          i++;
          continue;
        }
        int sum = array[i] + array[j] + array[k] + array[l];
        if (sum == target) {
          return true;
        } else if (sum < target) {
          i++;
        } else {
          j--;
        }
      }

      }
    }
    return false;
  }