最近在刷 LeetCode 上的題為找工作提前做準備享潜，在刷 Array 類問題的 Easy 難度的題的時候覺得還好，大部分的題還是能夠想得出來排龄，但是在刷到 Medium 難度的時候惜互，明顯感覺難度提升了吴菠，其中有一類題型連續(xù)出現(xiàn)引起了我的注意橄教，就是 K Sum 問題清寇。
K Sum問題就是喘漏，給出一個數(shù)作為 target，和一個數(shù)組作為待查數(shù)組华烟，在這個待查數(shù)組里找出 K 個數(shù)之和等于 target.
最簡單的 2 Sum
2 Sum應該是最簡單的了翩迈，但是它是解決我們后面 3 Sum和 4 Sum 問題的最小子問題了。如果一開始就用暴力循環(huán)的方法當然是做的出來盔夜，但是负饲，一是 LeetCode 可能會判超時(在 3 Sum 和 4 Sum 問題中確實會超時) ，二是暴力窮舉也沒什么意思喂链。最簡單的窮舉法是 O(n^2) 的時間復雜度返十，那么我們可以將數(shù)組排好序后，用頭尾兩個指針一次迭代即可找出椭微，時間復雜度降為了 O(nlogn).
3 Sum 問題
接下來就是3 Sum問題了吧慢，用暴力法 LeetCode 已經(jīng)給出了超時的提醒了，所以O(n^3)的時間復雜度肯定是不能接受的赏表，那么我們可以想像如何分解問題，畢竟3 Sum=2 Sum + 1 Sum匈仗，那么我們完全可以用將上面 2 Sum 問題的解法嵌入到一層循環(huán)中瓢剿，也就是先排序然后一個指針從頭開始循環(huán)，在數(shù)組的其他數(shù)中找出 2個數(shù)的和加上這個指針指向的數(shù)的和等于 target就行了悠轩，也就是說我們已經(jīng)有了循環(huán)指針指向的這個數(shù) V间狂，那么我們只需要在其他書中找出 num1+num2=target-V就行了，這就又把問題帶回到了2 Sum上火架，中不過多了一層循環(huán)鉴象，時間復雜度就降為了 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]) //跳過相同的數(shù)以避免相同的List的產(chǎn)生
{
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])//跳過相同的數(shù)
{
l++;
}
while(l<r&&nums[r]==nums[r-1])//跳過相同的數(shù)
{
r--;
}
l++;
r--;
}else if(target+nums[l]+nums[r]<0)//如果和小于0(target),l右移擴大和
{
l++;
}else//否則左移縮小和
{
r--;
}
}
}
}
3Sum Closest 問題
3Sum Closest 問題是3 Sum 問題的一個變種何鸡，意思就是給出一個 target纺弊，找出數(shù)組中最接近 target的 3 個數(shù)之和。這道題和 3 Sum 很像骡男，不同的是需要用一個臨時變量來保存當前最接近 target 的值，值得注意的是我們需要求 3個數(shù)的和減去 target 的差的絕對值來求最接近 target 的數(shù)。
/*
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 個數(shù)的和等于target朗儒，那么我們可以如法炮制，前面的3 Sum我們是固定一個數(shù)吮炕，然后求兩個數(shù)的和腊脱，將其分解為 2 Sum + 1 Sum，呢么 4 Sum 我們可以同樣的先固定兩個數(shù)龙亲，與另外兩個活動的數(shù)相加等于target陕凹，也就輸 4 Sum=3 Sum+1Sum悍抑。再在3 Sum的基礎上嵌套一層循環(huán)就可以達到目的了，時間復雜度也降低為了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++)//固定第一個數(shù)
{
if(i>0&&nums[i]==nums[i-1])//跳過相同的數(shù)
{
continue;
}
for(int j=i+1;j<nums.length-2;j++)//固定第二個數(shù)
{
if(j>i+1&&nums[j]==nums[j-1])//跳過相同的數(shù)
{
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 多到題传趾，發(fā)現(xiàn)一個規(guī)律，如果排序后不使用二分查找或者雙指針利用排序特性的話泥技，那么排序書沒有意義的浆兰，同時利用 Hash 特性也可以在增大空間復雜的同時減小時間復雜度。
