寻找和为定值的多个数

时间:2021-05-22 20:32:01

15.3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

题解

首先来思考如何寻找和为定值target的两个数,我们通常用的方法有
1. Hash,对每个a[i],通过hash表快速判断出target-a[i]是否在数列中,时间复杂度O(n),空间复杂度O(n)
2. 二分查找,在数列有序的前提下,对每个a[i],通过二分查找判断target-a[i]是否在数列中,时间复杂度O(nlogn),空间复杂度O(1)
3. 双指针, 用两个指针i,j,各自指向数组的首尾两端,依次判断a[i]+a[j]与的大小,大于target则j–,小于target则i++,无序时间复杂度O(nlogn),有序时间复杂度O(n),空间复杂度O(1)。

通过寻找两个数的方法我们可以很轻松地写出寻找三个数的方法,但要注意两点
1. 数字不能重复使用,即三个数的index(i,j,k)各不相同,可以简单的通过k>j>i来保证。
2. 结果没有重复,如-1,-1,0,1,为了避免出现两个[-1,0,1],我们希望对三个数中单独每一个数,都进行去重,即只有第一个-1有成为第一个数的机会。(为了方便去重,对数组进行了排序)

先是hash的方法,时间复杂度O(n^2),空间复杂度O(n)

public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
HashMap<Integer, Integer>map = new HashMap<>();
int len = nums.length;
for(int i = 0; i < len; i++){
//去除重复,只需保存最后出现的index
map.put(nums[i], i);
}

List<List<Integer>> haha = new ArrayList<>();
int rest = 0;
for(int i = 0; i < len - 2; i++){
//对第一个数去重
if(i > 0 && nums[i] == nums[i-1]) continue;
for(int j = i + 1; j < len - 1; j++){
//对第二个数去重
if(j > i + 1 && nums[j] == nums[j-1]) continue;
rest = 0 - nums[i] - nums[j];
if(map.containsKey(rest)){
//存在k大于j,保证数字没有重复使用
if(j < map.get(rest)){
haha.add(Arrays.asList(nums[i], nums[j], rest));
}
}
}
}
return haha;
}
}

在多个数时,排序的复杂度可以忽略,使用双指针法更为简便,时间复杂度O(n^2), 空间复杂度O(1)

public class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> haha = new ArrayList<>();
for(int i = 0; i < nums.length - 2; i++){
//对第一个数去重
if(i != 0 && nums[i] == nums[i-1]) continue;
int low = i + 1, high = nums.length - 1, sum = 0 - nums[i];
while(low < high){
if(nums[low] + nums[high] > sum) high--;
else if(nums[low] + nums[high] < sum) low++;
else{
haha.add(Arrays.asList(nums[i], nums[low], nums[high]));
//对第二、三个数去重
while(low < high && nums[low] == nums[low+1]) low++;
while(low < high && nums[high] == nums[high-1]) high--;
low++;
high--;
}
}
}
return haha;
}
}

对更多的数方法是类似的,如4Sum

public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> haha = new ArrayList<>();
for(int i = 0; i < nums.length - 3; i++){
//第一个数去重
if(i > 0 && nums[i] == nums[i-1]) continue;
for(int j = i + 1; j < nums.length - 2; j++){
//第二个数去重
if(j > i + 1 && nums[j] == nums[j-1]) continue;

int low = j + 1, high = nums.length - 1, sum = target - nums[i] - nums[j];
while(low < high){
if(nums[low] + nums[high] > sum) high--;
else if(nums[low] + nums[high] < sum) low++;
else{
haha.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));
//第三、四个数去重
while(low < high && nums[low] == nums[low+1]) low++;
while(low < high && nums[high] == nums[high-1]) high--;
low++;
high--;
}
}

}
}
return haha;
}
}