问题：K Sum问题是一个问题系列，在一个数组中找K个数的和能够满足题目中要求。从2 Sum 到 3 Sum , 3 Sum Clozet , 4 Sum。。解法虽一开始不容易想到，但get到解题技能后，该系列的题目其实解法较为单一。
一、核心解题思路。Two Sum。
题目：一个数组a中，找寻两个数，使其和等于target。返回两个数的下标。
思路：最白目的思路是O(n2)解法，无需多言。精彩的解法能够O(n)完成算法。
将该数组进行排序。设置两个指针start,end指向数组的头尾。如果a[start] + a[end] < target，那么将start指针往后移，因为当前的和值比目标值小；反之，将end指针向前移，因为当前的和值比目标值大。直到两个指针相遇，结束查找。
代码：由于要返回两个数的下标，因此在对数组进行排序之前，需要记录数据的原始下标。
1 public class Solution { 2 public int[] twoSum(int[] numbers, int target) { 3 4 if(numbers.length <= 1) return null; 5 6 Pair[] pairs = new Pair[numbers.length]; 7 for(int i = 0 ; i < numbers.length ; i++){ 8 pairs[i] = new Pair(numbers[i] , i+1); 9 } 10 11 Comparator<Pair> comparator = new Comparator<Pair>(){ 12 public int compare(Pair o1 , Pair o2){ 13 return o1.val > o2.val ? 1 : -1 ; 14 } 15 }; 16 17 Arrays.sort(pairs , comparator); 18 19 int index1 = 0 , index2 = numbers.length - 1; 20 21 while(index1 < index2){ 22 int temp = pairs[index1].val + pairs[index2].val; 23 if(temp == target) break; 24 else if(temp < target) index1++; 25 else index2--; 26 } 27 if(pairs[index1].index < pairs[index2].index) return new int[]{pairs[index1].index , pairs[index2].index}; 28 else return new int[]{pairs[index2].index , pairs[index1].index}; 29 } 30 } 31 32 class Pair{ 33 int val; 34 int index; 35 Pair(int x , int y){ 36 val = x; 37 index = y; 38 } 39 }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
二、举一反三。3 Sum。
问题：一个数组a，判断其中是否存在三个数a , b , c 使其和为target。返回这些三元组集合。
思路：该问题可退化为 2 Sum问题来解答。先选择任意一个数a ，然后判断剩余数组中是否存在另外两个数的和等于target - a。<----这里就完全是2 Sum问题的方法了。
代码：
1 public ArrayList<ArrayList<Integer>> threeSum(int[] num) { 2 3 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 4 5 Arrays.sort(num); 6 7 for(int i = 0 ; i < num.length ; i++){ 8 int target = 0 - num[i]; 9 //由于结果要求三元组的值要非递减顺序，因此将数组排序后，从头开始定第一个数据，后两个数据从该数据的后部选取。 10 for(int j = i + 1 , k = num.length - 1 ; j < num.length && k >= 0 && j < k ;){ 11 int temp = num[j] + num[k]; 12 if(temp == target){ 13 14 boolean ifAdd = true; 15 16 //judge duplicate 17 for(int index = 0 ; index < result.size() ; index++){ 18 if(result.get(index).get(0) == num[i] 19 && result.get(index).get(1) == num[j] 20 && result.get(index).get(2) == num[k]){ 21 ifAdd = false; 22 break; 23 } 24 } 25 if(ifAdd){ 26 ArrayList<Integer> one = new ArrayList<Integer>(); 27 one.add(num[i]); 28 one.add(num[j]); 29 one.add(num[k]); 30 result.add(one); 31 } 32 j++; 33 34 }else if(temp < target) j++; 35 else k--; 36 } 37 } 38 return result; 39 }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
三、练习熟悉。3 Sum Closest。
题目：给顶一个数组a，求最接近target的三元组的和。输出该和。
思路：完全与3 Sum问题相同。唯一不同的地方在于，因为它是判断与target最接近，因此利用绝对值来判断当前和是否与target最接近。
代码：
public int threeSumClosest(int[] num, int target) { Arrays.sort(num); int min = Integer.MAX_VALUE; for(int i = 0 ; i < num.length ; i++){ for(int j = i + 1 , k = num.length - 1 ; j < num.length && k >= 0 && j < k ;){ int threeSum = num[j] + num[k] + num[i]; if(threeSum == target) { min = 0; break; }else{ int dis = target - threeSum; //利用绝对值来判断是否与traget最接近。 if(Math.abs(dis) < Math.abs(min)) { min = dis; } if(dis > 0) j++; else k--; } } if(min == 0){ break; } } return target - min; }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
四、还是练习。4 Sum。
问题：一个数组a,寻找是否存在四个数a + b + c + d = target。返回四元组集合。
思路：先固定住一个数a ， 然后寻找剩余数组中是否存在三个数和 等于 target - a(退化为3Sum)，然后计算三个数和时，再先固定一个数b，然后寻找剩余数组中是否存在两个数和等于target-a -b(退化为2Sum)。
代码：
1 public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) { 2 3 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); 4 5 if(num.length <= 3) return result; 6 7 Arrays.sort(num); 8 9 for(int i = 0 ; i <= num.length - 4 ; i++){ 10 for(int j = i + 1 ; j <= num.length - 3 ; j++){ 11 int start = j + 1; 12 int end = num.length - 1; 13 while(start < end){ 14 int temp = num[i] + num[j] + num[start] + num[end]; 15 if(temp == target){ 16 boolean ifAdd = true; 17 for(int k = 0 ; k < result.size() ; k++){ 18 if(result.get(k).get(0) == num[i] && result.get(k).get(1) == num[j] 19 && result.get(k).get(2) == num[start] && result.get(k).get(3) == num[end]){ 20 ifAdd = false; 21 break; 22 } 23 } 24 25 if(ifAdd){ 26 ArrayList<Integer> each = new ArrayList<Integer>(); 27 each.add(num[i]); 28 each.add(num[j]); 29 each.add(num[start]); 30 each.add(num[end]); 31 result.add(each); 32 } 33 34 start++; 35 36 }else if(temp < target) start++; 37 else end--; 38 } 39 } 40 } 41 42 return result; 43 }
因此，总结K Sum的问题，其核心思路就是2Sum问题，任何K > 2时，都可通过逐层退化，到2Sum。而2Sum问题，在将数据进行排序后，就可通过两个指针来达到要求。