两数之和、三数之和、四数之和、K数之和

淡淡的烟草味﹌ 2024-04-17 19:48 16阅读 0赞

两数之和、三数之和、四数之和和K数之和是最近听室友提起的几道有意思的基础题，可以说是把双指针运用的淋漓尽致。（K数之和其实是一个动态规划的题，此处因为满足`*数之和`的的结构，放在一起对比提一下）。

# 1、两数之和等于Target的下标 #

**LintCode**：[https://www.lintcode.com/problem/two-sum/][https_www.lintcode.com_problem_two-sum]

**题目描述**：给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。假设只有一组答案。

你需要实现的函数twoSum需要**返回这两个数的下标**, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。

**简析**：此处需要返回的是数字所在位置的下标，不是判断是否存在。

第一种思路借助hashMap，key为数组中的值，value为其下标。遍历一次就可以找出目标答案，空间复杂度为O(n)，时间复杂度为O(n)；

第二种思路构造Pair类然后进行排序，排序之后通过头尾双指针找到目标答案，时间复杂度为O(nlogn)，空间复杂度为O(n)；

代码：

//方案一：自定义pair类,排序之后使用双指针 时间复杂度o(nlogn),空间复杂度o(1)
        // 并实现comparable接口-compare方法重写（当然也可以使用匿名内部类，继承comparator类，compare方法重写）
        
    public class Solution {
    
        class Pair implements Comparable<Pair>{
            public int key;
            public int value;
    
            Pair(int key, int value){
                this.key = key;
                this.value = value;
            }
    
            @Override
            public int compareTo(Pair o1){
                if(o1.value > this.value)
                    return -1;
                else if( o1.value == this.value)
                    return 0;
                else
                    return 1;
             }
        }  //end of Pair Class
        
        public int[] twoSum(int[] numbers, int target) {
            // write your code here
            int[] res = new int[2];
            if(numbers == null || numbers.length <= 1)
                return res;
            Pair[] pairs = new Pair[numbers.length];
            for(int i = 0; i < numbers.length; i ++){
                Pair pair = new Pair(i,numbers[i]);
                pairs[i] = pair;
            }
            Arrays.sort(pairs);
            int left = 0, right = numbers.length - 1;
            while(left < right){
                if(pairs[left].value + pairs[right].value == target){
                    res[0] = Math.min(pairs[left].key, pairs[right].key);
                    res[1] = Math.max(pairs[left].key, pairs[right].key);
                    left ++;
                    right --;
                }else if(pairs[left].value + pairs[right].value > target){
                    right --;
                }else
                left ++;
            }
            return res;
        }

//方法二：使用hashmap，此时不需要排序。时间复杂度o(n),空间复杂度o(n)
        //hashmap中存储键为数值，值为对应的数组下标
        
        public int[] twoSum2(int[] numbers, int target){
            if(numbers == null || numbers.length <= 1)
                return null;
            int[] res = new int[2];
            HashMap<Integer, Integer> map = new HashMap<>();  //key-numbers[i]  value- i
            for(int i = 0; i < numbers.length; i ++){
                //首先判断当前元素与前面的元素是否可以组成target
                if(map.keySet().contains(target - numbers[i])){
                    res[1] = i;
                    res[0] = map.get(target - numbers[i]); //另一个数的下标序号
                    return res; //只有一组结果，此处直接返回
                }
                map.put(numbers[i],i); //将当前元素加入到HashMap
            }
            return res;
        }

# 2、三数之和等于0的组合排列 #

**LintCode**：  
**题目描述**：给出一个有`n`个整数的数组`S`，在`S`中找到三个整数`a, b, c，`找到所有使得`a + b + c = 0`的三元组。在三元组`(a, b, c)`，要求`a <= b <= c`。结果不能包含重复的三元组。

**简析**：此题目`target`是固定等于`0`，那么要求的`a、b、c`中一定是正负相加或者全0。我们可以枚举首位a，然后用双指针遍历找出和为`target - a`的俩数。注意，要使用双指针必须首先保证有序性。

注意此题目要求输出的组合中不能有重复，所以要去重。去重的方法无非就是：枚举首位元素`a`的时候，保证不重复。当找到某组组合之后，第二位的元素和第三位的元素都需要去重。在有序数组中，该去重操作就是就是移到到下一位不想等的元素上。`a`元素如果发现已经被枚举过了，则将`a`元素指针i进行`i ++`，`b`元素如果之后重复是相等的，则不断后移，直到移到后面第一个不是该元素的位置上。实现起来就是`while(numbers[left] == numbers[left + 1]) left ++`，完成`while`循环之后，再加一个`left ++`。

代码：

public class Solution {
        /**
         * @param numbers: Give an array numbers of n integer
         * @return: Find all unique triplets in the array which gives the sum of zero.
         */
        public List<List<Integer>> threeSum(int[] numbers) {
            // write your code here
            
            //边界判断
            if(numbers == null || numbers.length == 0)
                return null;
            
            //返回的二维list
            List<List<Integer>> res = new ArrayList<>();
            
            //数组排序
            Arrays.sort(numbers);
            
            //枚举首位元素a + 双指针遍历
            for(int i = 0; i < numbers.length - 2 && numbers[i] <= 0; i ++){
                
                //首位元素去重
                while(i >= 1 && i < numbers.length - 2 && numbers[i] == numbers[i - 1])
                    i ++;
                int left = i + 1;
                int right = numbers.length - 1;
                //left < right 同时约束了指针的范围，避免了 i++ 越界
                while(left < right){ 
                    if(numbers[i] + numbers[left] + numbers[right] == 0){
                        List<Integer> tmp =  new ArrayList<>();
                        tmp.add(numbers[i]);
                        tmp.add(numbers[left]);
                        tmp.add(numbers[right]);
                        res.add(tmp);
                        //第二位元素去重
                        while(left + 1 < right && numbers[left] == numbers[left + 1])
                            left ++;
                        //第三位元素去重
                        while(left < right - 1 && numbers[right] == numbers[right - 1])
                            right --;
                         //注意！！去重结束之后仍要同时移动left和right指针
                         //保证指针移动到了第一个不是重复元素的位置上
                        left ++; right --;    
                    }else if(numbers[i] + numbers[left] + numbers[right] > 0)
                        right --;
                    else
                        left ++;    
                }
            }
            
            return res;
        }
    }

# 3、三数之和小于Target的组合总数目 #

**LintCode**: [https://www.lintcode.com/problem/3sum-smaller/description][https_www.lintcode.com_problem_3sum-smaller_description]

**题目描述**：给定一个`n`个整数的数组和一个目标整数`target`，找到下标为`i、j、k`的数组元素`0 <= i < j < k < n`，满足条件`nums[i] + nums[j] + nums[k] < target`。输出满足上述条件的组合的总数。

**简析**：需要找和为target的三个数，可以首先确定一个数A，然后找和为target-A的两个数。

(错误思路：“从数学角度来看，三个数和为target，一定至少有1个小于等于target的数。所以可以A数的范围定在<= target的范围进行枚举，剩余两数则在大于A的范围内进行双指针遍历”。 这种想法非常非常错误的，比如`target= (-4) = (-2) + (-2) + 0`，三个数都比target要大。当target为0和正数的时候，刚才的说法才是正确的。）

通过剖析上面的错误思路，对于首位数字的枚举，不能仅仅只枚举小于等于target的数，应该遍历到数组中所有的数，也就是从\[0, length -3\]，最后两位要留给剩余两个数字。

**代码**：

public class Solution {
        /**
         * @param nums:  an array of n integers
         * @param target: a target
         * @return: the number of index triplets satisfy the condition nums[i] + nums[j] + nums[k] < target
         */
        public int threeSumSmaller(int[] nums, int target) {
            // Write your code here
            int cnt = 0;
            if(nums == null || nums.length == 0)
                return cnt;
            //数组排序后方可使用双指针
            Arrays.sort(nums);
    
            //枚举首位数字
            for(int i = 0; i <= nums.length - 3; i ++){
                int left = i + 1;
                int right = nums.length - 1;
                //确定首位数字后，双指针遍历
                while(left < right){
                   //当和小于target时：保持当前left不变，right指针从此处前移到left+1，所有的和都将小于target
                   //所以此时满足条件的情况的数目等于 right - (left + 1) + 1 = right - left
                    if(nums[left] + nums[right] < target - nums[i]){ 
                        cnt += right - left;  
                        left ++;
                    }else
                        right --;
                }
            }
            return cnt;
        }
    }

# 4、四叔之和等于Target的组合 #

**LintCode**:[https://www.lintcode.com/problem/4sum/description][https_www.lintcode.com_problem_4sum_description]

**题目描述**：给一个包含`n`个数的整数数组`S`，在`S`中找到所有使得和为给定整数`target`的四元组`(a, b, c, d)`。四元组`(a, b, c, d)`中，需要满足`a <= b <= c <= d`。答案中不可以包含重复的四元组。

**简析**：四数之和在三数之和的基础上又多了一个数字，仍旧使用双指针，此时需要枚举前两个元素`a`和`b`，双指针寻找`c`和`d`，是的`c + d = target - a - b`。在有序数组中的去重仍旧采用移动指针的方法，直到移动到第一个不相等的位置。

具体来说，在处理的时候要注意两个问题：1.数组越界 2.去重遍历的范围。

例如对第一个元素来说，`i`本身的范围是`[0, numbers.length - 4]`，但是当他处理0位置时候，不需要和前面的元素判重。判重的范围是`[1, numbers.length - 4]`，例如第1位置的数值与第0位置的数值相等，则需要跳过第1位置。

针对第二个元素，j本身的范围是`[i + 1, numbers.length -3]`。和第一个元素一样，他判重的范围是包含`i + 1`的。从`i + 2`位置开始，如果和前面元素相等，则需要跳过。

针对第三个和第四个元素而言，当出现满足要求的组合时候，就要进行去重，分别把left和`right`指针移动到不等于当前指针的第一个位置。移动指针过程中非常容易出现数组越界，在`while(left < right)`的循环中，要保证`left`指针`left ++`后都要小于`right`，`right`指针保证`right --` 要大于`left`。

**代码：**

public class Solution {
        /**
         * @param numbers: Give an array
         * @param target: An integer
         * @return: Find all unique quadruplets in the array which gives the sum of zero
         */
        public List<List<Integer>> fourSum(int[] numbers, int target) {
            // write your code here
            List<List<Integer>> res = new ArrayList<>();
            if(numbers == null || numbers.length == 0)
                return res;
            
            Arrays.sort(numbers);
            //a元素遍历
            for(int i = 0; i < numbers.length - 3; i ++){
                
                //a元素去重
                while(i > 0 && i <  numbers.length - 3 && numbers[i] == numbers[i - 1])
                    i ++;
                //b元素遍历
                for(int j = i + 1; j < numbers.length - 2; j ++){
                    
                    //b元素去重
                    while(j > i + 1 &&  j < numbers.length - 2 && numbers[j] == numbers[j - 1])
                        j ++;
                        
                    //双指针
                    int left = j + 1;
                    int right  = numbers.length - 1;
                    while(left < right){
                        if(numbers[left] + numbers[right] + numbers[i] + numbers[j] == target){
                            List<Integer> tmp = new ArrayList<>();
                            tmp.add(numbers[i]); 
                            tmp.add(numbers[j]); 
                            tmp.add(numbers[left]); 
                            tmp.add(numbers[right]);
                            res.add(tmp);
                            //第三个元素去重
                            while(left + 1 < right && numbers[left + 1] == numbers[left])
                                left ++;
                             //第四个元素去重   
                            while(left < right - 1 && numbers[right] == numbers[right - 1])
                                right --;
                            left ++; right --;    
                        }else if(numbers[left] + numbers[right] + numbers[i] + numbers[j] < target)
                            left ++;
                        else
                            right --;
                    }
                }
            }        
            return res;
        }
    }

# 5、K数之和 #

> 此题目与上面的题目都是同一类型的，前面的题都是双指针的。此题目虽然是k数之和，看起来像三数之和、四数之和的拓展。但其实是动态规划的问题。

**LintCode**: [https://www.lintcode.com/problem/k-sum/][https_www.lintcode.com_problem_k-sum]

**题目描述**：给定 n 个不同的正整数，整数 k（k <= n）以及一个目标数字 target。　  
在这 n 个数里面找出 k 个数，使得这 k 个数的和等于目标数字，求问有多少种方案？  
输入:  
List = \[1,2,3,4\] ； k = 2 ； target = 5  
输出: 2  
说明: 1 + 4 = 2 + 3 = 5

**简析**：设状态为`f[i][j][p]`，表示前i个数中找出j个数且和等于p的方案数目。

那么状态转移方程： `f[i][j][p] = f[i - 1][j][p] + f[i - 1][j - 1][p -num[i]]`

最终返回`f[n][k][target]`即可

**代码**：

public class Solution {
        /**
         * @param A: An integer array
         * @param k: A positive integer (k <= length(A))
         * @param target: An integer
         * @return: An integer
         */
        public int kSum(int[] A, int k, int target) {
            // write your code here
            if(A == null || A.length ==0 || k <= 0)
                return 0;
            //正整数的总数从0 - A.length； 可选的个数从 0 - k; target也是从 0 - target
            int[][][] f = new int[A.length + 1][ k + 1][target + 1];
            //初始值
            for(int i = 0; i <= A.length; i ++){
                f[i][0][0] = 1;
            }
            //f[i][j][t] = f[i - 1][j][t] + f[i - 1][j - 1][t -A[i]]
            for(int i = 1; i <= A.length; i ++)
                for(int j = 1; j <= k; j ++)
                    for(int t = 1; t <= target; t ++){
                        f[i][j][t] = f[i - 1][j][t];
                        f[i][j][t] += t - A[i - 1] >=0 ? f[i - 1][j - 1][t -A[i - 1]] : 0;
                    }
            return f[A.length][k][target];
        }
    }

[https_www.lintcode.com_problem_two-sum]: https://www.lintcode.com/problem/two-sum/
[https_www.lintcode.com_problem_3sum-smaller_description]: https://www.lintcode.com/problem/3sum-smaller/description
[https_www.lintcode.com_problem_4sum_description]: https://www.lintcode.com/problem/4sum/description
[https_www.lintcode.com_problem_k-sum]: https://www.lintcode.com/problem/k-sum/