面试题 16.24. 数对和

题目

设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。

示例 1: 输入: nums = [5,6,5], target = 11
输出: [[5,6]]

示例 2: 输入: nums = [5,6,5,6], target = 11
输出: [[5,6],[5,6]]

提示：

  • nums.length <= 100000

题解

public List<List<Integer>> pairSums(int[] nums, int target) {
    Arrays.sort(nums);

    List<List<Integer>> result = new ArrayList<>();
    int start = 0, end = nums.length - 1;

    // 双指针
    while (start < end) {
        int sum = nums[start] + nums[end];
        if (sum < target) {
            start++;
        } else if (sum > target) {
            end--;
        } else {
            result.add(Arrays.asList(nums[start], nums[end]));
            start++;
            end--;
        }
    }

    return result;
}