Given three arrays, determine if a set can be made by picking one element from each array that sums to the given target number.

Assumptions

• The three given arrays are not null and have length of at least 1

Examples

• A = {1, 3, 5}, B = {8, 2}, C = {3}, target = 14, return true(pick 3 from A, pick 8 from B and pick 3 from C)

Solution: 遍历A, 把target - A[i]当作新target，在B和C中找

  public boolean exist(int[] a, int[] b, int[] c, int target) {
    Set<Integer> hashset = new HashSet<>();
    Set<Integer> hashset2 = new HashSet<>();
    for (int num : b) {
      hashset2.add(num);
    }
    for (int num : a) {
      if (hashset.contains(num)) {
        continue;
      }
      hashset.add(num);
      int tar = target - num;
      for (int num2 : c) {
        if (hashset2.contains(tar - num2)) {
          return true;
        }
      }
    }
    return false;
  }

不能用三指针谁小移谁的方法，eg: [-1, 0, 1], [2, 3, 7], [4, 9], target: 15. -1+7+9=15

  //wrong
  public boolean exist(int[] a, int[] b, int[] c, int target) {
    Arrays.sort(a);
    Arrays.sort(b);
    Arrays.sort(c);
    int i = 0, j = 0, k = 0;
    while (i < a.length && j < b.length && k < c.length) {
      int sum = a[i] + b[j] + c[k];
      if (sum == target) {
        return true;
      } else if (sum < target) {
        if (a[i] <= b[j] && a[i] <= c[k]) {
          i++;
        } else if (b[j] <= a[i] && b[j] <= c[k]) {
          j++;
        } else {
          k++;
        }
      } else {
        return false;
      }
    }
    return false;
  }