Find all pairs of elements in a given array that sum to the pair the given target number. Return all thedistinctpairs of values.

Assumptions

• The given array is not null and has length of at least 2
• The order of the values in the pair does not matter

Examples

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

Solution: i应取duplicates的第一个，j应取duplicates的最后一个，以免跳过了情况

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

better way: 对duplicates只移动i。并且while里用if，不是while，不然里层while结束后还要判断边界条件

用hashmap: 注意2*x == target的情况