设计一个算法,找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
示例 1:
输入: nums = [5,6,5], target = 11
输出: [[5,6]]
示例 2:
输入: nums = [5,6,5,6], target = 11
输出: [[5,6],[5,6]]
提示:
nums.length <= 100000
排序,双指针思想
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class PairSumsTest {
public static void main(String[] args) {
int [] nums={5,6,5,6};
int target=11;
List<List<Integer>> listList = pairSums(nums, target);
System.out.println("listList = " + listList);
}
public static List<List<Integer>> pairSums(int[] nums, int target) {
List<List<Integer>> listList = new ArrayList<>();
if (nums == null || nums.length < 2) {
return listList;
}
Arrays.sort(nums);
int start = 0;
int end = nums.length - 1;
while (start < end) {
List<Integer> list = new ArrayList<>();
if (nums[start] + nums[end] == target) {
list.add(nums[start]);
list.add(nums[end]);
listList.add(list);
start++;
end--;
} else if (nums[start] + nums[end] < target) {
start++;
} else {
end--;
}
}
return listList;
}
}
好久没有写类似的题解了,这题基于数组排序+双指针的思想进行解决,目前自己正在慢慢把已经做过的内容进行输出,其实也算是一种对往日题解的回顾吧,目前已输出一百多道题解了,还在继续~
算法汇总:leetcode刷题汇总(非最终版)