最近在刷 LeetCode 上的题为找工作提前做准备，在刷 Array 类问题的 Easy 难度的题的时候觉得还好，大部分的题还是能够想得出来，但是在刷到 Medium 难度的时候，明显感觉难度提升了，其中有一类题型连续出现引起了我的注意，就是 K Sum 问题。
K Sum问题就是，给出一个数作为 target，和一个数组作为待查数组，在这个待查数组里找出 K 个数之和等于 target.
最简单的 2 Sum
2 Sum应该是最简单的了，但是它是解决我们后面 3 Sum和 4 Sum 问题的最小子问题了。如果一开始就用暴力循环的方法当然是做的出来，但是，一是 LeetCode 可能会判超时(在 3 Sum 和 4 Sum 问题中确实会超时) ，二是暴力穷举也没什么意思。最简单的穷举法是 O(n^2) 的时间复杂度，那么我们可以将数组排好序后，用头尾两个指针一次迭代即可找出，时间复杂度降为了 O(nlogn).
3 Sum 问题
接下来就是3 Sum问题了，用暴力法 LeetCode 已经给出了超时的提醒了，所以O(n^3)的时间复杂度肯定是不能接受的，那么我们可以想像如何分解问题，毕竟3 Sum=2 Sum + 1 Sum，那么我们完全可以用将上面 2 Sum 问题的解法嵌入到一层循环中，也就是先排序然后一个指针从头开始循环，在数组的其他数中找出 2个数的和加上这个指针指向的数的和等于 target就行了，也就是说我们已经有了循环指针指向的这个数 V，那么我们只需要在其他书中找出 num1+num2=target-V就行了，这就又把问题带回到了2 Sum上，中不过多了一层循环，时间复杂度就降为了 O(n^2)。
代码实例：
/*注题目
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.
*/
public class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++)
{
if(i>0&&nums[i]==nums[i-1]) //跳过相同的数以避免相同的List的产生
{
continue;
}
find(result,nums,i+1,nums.length-1,nums[i]);
}
return result;
}
public static void find(List<List<Integer>> res,int[] nums,int start,int end,int target)
{
int l=start,r=end;
while(l<r)
{
if(target+nums[l]+nums[r]==0)
{
List<Integer> list=new ArrayList<>();
list.add(target);
list.add(nums[l]);
list.add(nums[r]);
res.add(list);
while(l<r&&nums[l]==nums[l+1])//跳过相同的数
{
l++;
}
while(l<r&&nums[r]==nums[r-1])//跳过相同的数
{
r--;
}
l++;
r--;
}else if(target+nums[l]+nums[r]<0)//如果和小于0(target),l右移扩大和
{
l++;
}else//否则左移缩小和
{
r--;
}
}
}
}
3Sum Closest 问题
3Sum Closest 问题是3 Sum 问题的一个变种，意思就是给出一个 target，找出数组中最接近 target的 3 个数之和。这道题和 3 Sum 很像，不同的是需要用一个临时变量来保存当前最接近 target 的值，值得注意的是我们需要求 3个数的和减去 target 的差的绝对值来求最接近 target 的数。
/*
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
*/
public class Solution {
public static int threeSumClosest(int[] nums, int target) {
int result=Integer.MAX_VALUE;//用来保存当前最接近target的值
Arrays.sort(nums);
for(int i=0;i<nums.length-2;i++)
{
int temp=find(nums,i+1,nums.length-1,target,nums[i]);
if(i==0)
{
result=temp;
continue;
}
if(Math.abs(temp-target)<Math.abs(result-target))
{
result=temp;
}
}
return result;
}
public static int find(int[] nums,int start,int end,int target,int curV)
{
int result=Integer.MAX_VALUE;
int l=start,r=end;
int c=Integer.MAX_VALUE;
while(l<r&&c!=0)
{
if(Math.abs(curV+nums[l]+nums[r]-target)<c)
{
result =curV+nums[l]+nums[r];
c=Math.abs(curV+nums[l]+nums[r]-target);
}
if(curV+nums[l]+nums[r]>target)
{
r--;
}else
{
l++;
}
}
return result;
}
}
4 Sum 问题
4 Sum问题也显而易见了，就是求 4 个数的和等于target，那么我们可以如法炮制，前面的3 Sum我们是固定一个数，然后求两个数的和，将其分解为 2 Sum + 1 Sum，呢么 4 Sum 我们可以同样的先固定两个数，与另外两个活动的数相加等于target，也就输 4 Sum=3 Sum+1Sum。再在3 Sum的基础上嵌套一层循环就可以达到目的了，时间复杂度也降低为了O(n^3)。
/*
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note: The solution set must not contain duplicate quadruplets.
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
*/
public class Solution {
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res=new ArrayList<>();
Arrays.sort(nums);
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;
}
find(nums,res,j+1,nums.length-1,target,nums[i],nums[j]);
}
}
return res;
}
public static void find(int[] nums,List<List<Integer>> res,int start,int end,int target,int v1,int v2)
{
int l=start,r=end;
while(l<r)
{
if(nums[l]+nums[r]+v1+v2==target)
{
List<Integer> list=new ArrayList<>();
list.add(nums[l]);
list.add(nums[r]);
list.add(v1);
list.add(v2);
res.add(list);
while(l<r&&nums[l]==nums[l+1])
{
l++;
}
while(l<r&&nums[r]==nums[r-1])
{
r--;
}
l++;
r--;
}else if(nums[l]+nums[r]+v1+v2<target)
{
l++;
}else
{
r--;
}
}
}
}
总结
做了 30 多到题，发现一个规律，如果排序后不使用二分查找或者双指针利用排序特性的话，那么排序书没有意义的，同时利用 Hash 特性也可以在增大空间复杂的同时减小时间复杂度。
网友评论