算法6--SumK问题

整理总结一下与sumK有关的问题。

1.两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
使用一个map用来存储数组元素值以及下标索引，遍历整个数组，查询map中是否存在target-nums[i]使得和nums[i]之和等于target.(需要考虑数值与索引时，一般使用map映射来解决)  时间复杂度N

public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            if(map.get(target-nums[i])!=null)
                return new int[]{i, map.get(target-nums[i])};
            else
                map.put(nums[i], i);
        }
        return new int[]{-1, -1};
    }

2.三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题目要求所有三元组都不重复，首先排序整个数组，从头遍历数组，当固定一个元素时，采用头尾指针，分别从该数位置以及尾部位置进行移动，使得两个指针所指数字之和等于固定元素的相反数即可。当找到一组符合条件的元祖，指针应该继续移动越过所有相等的值，避免最后的三元组是重复的。时间复杂度NlogN

public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ll = new ArrayList<>();
        List<Integer> l = null;
        Arrays.sort(nums);
        for(int k=0; k<nums.length; k++){
            if (nums[k] > 0) break;
            //当第一个数重复时，移动下一个位置寻找
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1;
            int j = nums.length - 1;
            while(i<j){
                int sum = nums[i]+nums[j]+nums[k];
                //如果找到加入到ll 并且继续移动取出重复值
                if(sum==0){                    
                    ll.add(new ArrayList<>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i<j && nums[i+1]==nums[i]) i++;
                    while(i<j && nums[j-1]==nums[j]) j--;
                    i++;
                    j--;
                }else if(sum>0){
                    j--;
                }else{
                    i++;
                }
            }
        }
        return ll;
    }

3.最接近三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
维护一个差值变量来记录当前最小差值，如果三者之和等于目标值直接返回；如果差值小于当前差值，则更新最小差值和最接近值；根据三者之和与目标值的大小关系来移动头尾指针，遍历数组，来找到最小值。时间复杂度NlogN

public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        int diff = Integer.MAX_VALUE;
        for(int k=0; k<nums.length-2; k++){
            int i=k+1;
            int j=nums.length-1;
            while(i<j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum==target){
                    return sum;
                }
                int diff_temp = Math.abs(sum-target);                        
                if(diff_temp<diff){
                    min = sum;
                    diff = diff_temp;
                }
                if(sum>target){
                    j--;
                }else{
                    i++;
                }
            }
        }
        return min; 
    }

4.四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

在三数之和基础之上，外两层维护两个循环，最里层维护两个指针来进行移动寻找时间复杂度  N2logN

public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ll = new ArrayList<>();
        Arrays.sort(nums);
        for(int k=0; k<nums.length; k++){
            //if(nums[k]>target) break;
            if(k>=1 && nums[k]==nums[k-1]) continue;
            for(int m=k+1; m<nums.length; m++){
                //if(nums[m]>target-nums[k]) break;
                if(m>=k+2 && nums[m]==nums[m-1]) continue;
                int i=m+1;
                int j=nums.length-1;
                while(i<j){
                    int sum = nums[k] + nums[m] + nums[i] + nums[j];
                    if(sum==target){
                        ll.add(new ArrayList<>(Arrays.asList(nums[k], nums[m], nums[i], nums[j])));
                        while(i<j && nums[i]==nums[i+1]) i++;
                        while(i<j && nums[j]==nums[j-1]) j--;
                        i++;
                        j--;
                    }else if(sum>target){
                        j--;
                    }else{
                        i++;
                    }
                }
            }
        }
        return ll;
    }

5.Sum K问题

返回数组中k个元素之和等于target的不重复元组

首先将数组排序，将K情况转化为K-1情况，利用递归来解决，最终基本情况为K==2.

public List<List<Integer>> sum(int[] nums, int target, int k){
        int length = nums.length;
        List<List<Integer>> ll = new ArrayList<>();
        List<Integer> l = new ArrayList<>();
        Arrays.sort(nums);
        if (k < 2) return null;
        sumK(nums, k, target, 0, length - 1, l, ll);
        return ll;
    }

	public static void sumK(int[] nums, int k, int target, int from, int end, List<Integer> l, List<List<Integer>> ll){
		if(k==2){
			sum2(nums, target, from, end, ll);
		}else{
			for(int i = from; i < end - k + 2; i++){
                int temp = k;
                int large = 0;
                int small = 0;
                while (temp > 0){
                    large += nums[end - temp + 1];
                    small += nums[from + temp - 1];
                    temp--;
                }
                if(small > target) return;
                if(large < target) return;
                if(i > from && nums[i] == nums[i - 1]) continue;
                l.add(nums[i]);
                sumK(nums, k - 1, target - nums[i], i + 1, end, l, ll);
                l.remove(l.size() - 1);
            }
		}
	}
	public static void sum2(int[] nums, int target, int from, int end, List<List<Integer>> ll){
		int left = from;
		int right = end;
		while(left<right){
			int sum = nums[left] + nums[right];
			if(sum==target){
				ll.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
			}else if(sum>target){
				right--;
			}else{
				left++;
			}
		}
	}