16.24. 数对和

Posted on | In
Words count in article: 258 | Reading time ≈ 1

题目

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

示例1：

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

示例2：

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

解法

解法一：

借助HaspMap

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> pairSums(int[] nums, int target) {
		Map<Integer, Integer> map = new HashMap<>();

		List<List<Integer>> ans = new ArrayList<>();
		for (int num : nums) {
			Integer count = map.get(target - num);
			if (count != null) {
				ans.add(Arrays.asList(num, target - num));
				if (count == 1) {
					map.remove(target - num);
				} else {
					map.put(target - num, --count);
				}
			} else {
				map.put(num, map.getOrDefault(num, 0) + 1);
			}
		}
		return ans;
	}

解法二：

排序+双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> pairSums(int[] nums, int target) {
		Arrays.sort(nums);
		List<List<Integer>> ans = new LinkedList<>();
		int left = 0;
		int right = nums.length - 1;
		while (left < right) {
			int sum = nums[left] + nums[right];
			if (sum < target) {
				++left;
			} else if (sum > target) {
				--right;
			} else {
				ans.add(Arrays.asList(nums[left++], nums[right--]));
			}
		}
		return ans;
	}
0%