两数、三数、四数之和
整体的题意是，在一个乱序的数组中，找到2个（或3个、4个）数，使得它们的和恰好等于目标值。
LeetCode上的题目，有的是返回数组的下标，有的是返回数字本身
两数之和
LeetCode上的本题只要返回一组解，所以不需要考虑重不重复的问题。
如果使用两次遍历，就需要 的时间复杂度。
这样太慢了点，我们不妨把已经遍历过的数字及位置存起来，之后我们查询它在不在，如果在，就输出结果。
class Solution {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[] {map.get(target - nums[i]) ,i};
}
map.put(nums[i], i);
}
return new int[] {1,1};
}
}
三数之和
这道题要求返回所有解，且不重复。
刚才的两数之和我们把 的问题优化到了
。这道题乍一看三层循环，要
，我们看看能不能优化为
呢？
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int target = 0;
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
// 下面就类似于二数之和
Set<Integer> set = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
if (set.contains(target - nums[i] - nums[j])) {
System.out.println(i + ", " + j);
List<Integer> one = new ArrayList<>();
one.add(nums[i]);
one.add(nums[j]);
one.add(target - nums[i] - nums[j]);
ans.add(one);
}
set.add(nums[j]);
}
}
return ans;
}
}
上述解满足了 的时间复杂度，但是不难去除重复解。不符合LeetCode的题意。
虽然可以再用一个 Set 来去重复，但是未免又浪费了空间复杂度。
上面的代码用模仿二数之和的思路，用 HashSet 来把第二层、第三层循环优化为一次循环。
除了 HashSet 之外，对于有序数组，还可以用双指针的方法来把两次循环优化为一次循环。（在1.两数之和中，如果排序，反而浪费了时间。）
public class Solution {
public static void main(String[] args) {
threeSum(new int[]{-1, 0, 1, 2, -1, -4});
}
public static List<List<Integer>> threeSum(int[] nums) {
int target = 0;
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums); // 排序
for (int i = 0; i < nums.length; i++) {
while (i > 0 && i < nums.length && nums[i] == nums[i - 1]) {
i++;
}
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
// 如果等于目标，就添加答案
if (nums[i] + nums[j] + nums[k] == target) {
List<Integer> one = new ArrayList<>();
one.add(nums[i]);
one.add(nums[j]);
one.add(nums[k]);
ans.add(one);
// 移动k和j，避免重复
while (j < k && nums[j] == nums[j + 1]) {
++j;
}
while (j < k && nums[k] == nums[k - 1]) {
--k;
}
++j;
--k;
} else if (nums[i] + nums[j] + nums[k] > target) {
--k;
} else {
++j;
}
}
}
return ans;
}
}
最接近的三数之和
和三数之和类似，每次保存最接近的结果。
因为输出结果就是一个最接近的值，所以无所谓考虑重不重复。
class Solution {
public int threeSumClosest(int[] nums, int target) {
int ans = Integer.MAX_VALUE;
Arrays.sort(nums); // 排序
for (int i = 0; i < nums.length; i++) {
while (i > 0 && i < nums.length && nums[i] == nums[i - 1]) {
i++;
}
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果等于目标，就直接是答案
if (sum == target) {
return sum;
}
// 更新结果
if (Math.abs(target - sum) < Math.abs(target - ans)) {
ans = sum;
}
if (nums[i] + nums[j] + nums[k] > target) {
--k;
} else {
++j;
}
}
}
return ans;
}
}
四数之和
和三数之和类似，最后面两层也是用双指针的思路。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int k = j + 1;
int l = nums.length - 1;
while (k < l) {
long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
// 如果等于目标
if (sum == target) {
List<Integer> one = new ArrayList<>();
one.add(nums[i]);
one.add(nums[j]);
one.add(nums[k]);
one.add(nums[l]);
ans.add(one);
// 去重复
while (k < l && nums[k] == nums[k + 1]) {
++k;
}
++k;
while (k < l && nums[l] == nums[l - 1]) {
--l;
}
--l;
} else if (sum < target) {
++k;
} else {
--l;
}
}
}
}
return ans;
}
}
如此，原本四重循环的时间复杂度 优化为
。
小结
数之和如果暴力，需要
重循环，时间复杂度
。可以采用 HashSet 或双指针的方法，将其降为
。
-
如果需要考虑不重复，那么就只能用双指针的方法。双指针要求对数组
nums进行排序，本身就有的时间复杂度。所以“两数之和”是不使用双指针的（除非数已经排序好了）。
-
如果用 HashSet，则不需要排序，省了一个排序的时间。但是会造成重复。
网友评论