leetcode 15.3Sum & 16.Sum Closest & 18.4Sum

2017-08-15

题意

寻找三个数a,b,c。使得a+b+c=0。找到所有的不重复的组合。注意[-1,1,0]和[1,-1,0]是重复的。

返回所有组合为0的列表数组。

我的想法

容易想到法子是暴力法。遍历所有的三个子串，然后如果相加的和等于0，加入列表。每次加入列表还需判重。这个效率是O(n^3)显然是会超时的。

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>(1000);
        for(int i = 0;i<=nums.length-3;i++){
            for(int j = i+1;j<=nums.length-2;j++){
                for(int k=j+1;k<=nums.length-1;k++){
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> list = new ArrayList<Integer>(3);
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[k]);
                        boolean flag = false;
                        for(int m=0;m<lists.size();m++){
                            ArrayList<Integer> slist = new ArrayList<Integer>(3);
                            slist = (ArrayList<Integer>)lists.get(m);
                            ArrayList<Integer> tlist = (ArrayList<Integer>)slist.clone();
                            if(tlist.indexOf(nums[i])!=-1){
                                tlist.remove(tlist.indexOf(nums[i]));
                                if(tlist.indexOf(nums[j])!=-1) {
                                    flag = true;
                                    break;
                                }    
                            }
                        }
                        if(!flag) lists.add(list);
                        break;
                    }
                }
            }
        }
        return lists;
    }
}

如何优化呢？

大神思路

关于K-sum问题，有一个通解方式使得暴力法的复杂程度O(n^k^)降低到O(n^(k-1)^)。

首先：把整个数组排序（ASC），实现复杂度为O(nlogn)

第二步：按住k-2个数，另外两个数分别从排好序的数组两端找如果大于目标数，右标左移动，反之移动左标。注意要避开之前固定的k-2个数。

排序带来最大的好处就是可以帮助去重，如果当前固定的元素和上个已经做了查找的数相同，就可以过滤掉了。而且可以从按住的数的后面开始找。想想是为什么？

下面是我用大神思路实现的代码

优化后代码

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //这里初始化ArrayList的时候假设了数组的长度，减少了ArrayList在增加容量的时候的数组克隆操作
        List<List<Integer>> lists = new ArrayList<List<Integer>>(10000);
        Arrays.sort(nums);
        for(int i = 0;i<nums.length;i++){
        //去掉重复判断
            if(i>0&&nums[i] == nums[i-1]) continue;
            int start = i+1;
            int end = nums.length-1;
            int target = 0 - nums[i];
            while(start<end){
                if(nums[start]+nums[end]>target){
                  end--;continue;  
                }
                if(nums[start]+nums[end]<target){
                  start++;continue;  
                }
                if(nums[start]+nums[end]==target){
                    List<Integer> list = new ArrayList<Integer>(3);
                    list.add(nums[i]);
                    list.add(nums[start]);
                    list.add(nums[end]);
                    lists.add(list);
                    do{
                        start++;    
                    }while(start < nums.length &&nums[start]==nums[start-1]);
                    do{
                        end--;
                    }while(end > 0 &&nums[end]==nums[end+1]);
                }
            }
        }
        return lists;
    }

}

有了上述思路后，同类题16-3Sum Closest 和 18-4Sum 都可以迎刃而解

16.3Sum Closest题意

和3Sum题目类似，只是这里需要输入一个target，找出最接近target的3个数解。你可以假定这个解有且只存在一个。

16.3Sum Closest我的思路和代码

其实和3Sum类似，只需在查到和target相等时，直接返回。

查到和target不相等时，记录和target之间的差值。找到最小差值。

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int gap = Integer.MAX_VALUE;
        int res = 0;
        Arrays.sort(nums);
        for(int i = 0;i<nums.length-2;i++){
            if(i>0&&nums[i] == nums[i-1]) continue;
            int start = i+1;
            int end = nums.length-1;
            while(start<end){
                if(nums[i]+nums[start]+nums[end]==target){
                    return target;
                }else{
                    if(Math.abs(target-(nums[i]+nums[start]+nums[end]))<gap){
                        gap = Math.abs(target-(nums[i]+nums[start]+nums[end]));
                        res = nums[i]+nums[start]+nums[end];
                    }
                    if(nums[i]+nums[start]+nums[end]>target) {
                        end--;
                        continue;
                    }
                    if(nums[i]+nums[start]+nums[end]<target) start++;
                    continue;

                }
            }
        }
        return res;
    }
}

18.4Sum 题意

和3Sum一样，只是从3个数提升到了4个数。不是找到和等于0，而是等于输入的target。

18.4Sum 我的代码

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>(10000);
        Arrays.sort(nums);
        for(int i=0;i<nums.length-3;i++){
             if(i>0&&nums[i] == nums[i-1]) continue;
            lists = threeSum(nums[i],nums,lists,i,target-nums[i]);
        }
        return lists;
    }
    public List<List<Integer>> threeSum(int num1,int nums[],List<List<Integer>> lists,int index,int tar){
        for(int j=index+1;j<nums.length-2;j++){
            if(j>index+1&&nums[j] == nums[j-1]) continue;
            int start = j+1;
            int end = nums.length-1;
            while(start<end){
                if(nums[j]+nums[start]+nums[end]>tar){
                  end--;continue;  
                }
                if(nums[j]+nums[start]+nums[end]<tar){
                  start++;continue;  
                }
                if(nums[j]+nums[start]+nums[end]==tar){
                    List<Integer> list = new ArrayList<Integer>(4);
                    list.add(nums[index]);
                    list.add(nums[j]);
                    list.add(nums[start]);
                    list.add(nums[end]);
                    lists.add(list);
                    do{
                        start++;    
                    }while(start < nums.length &&nums[start]==nums[start-1]);
                    do{
                        end--;
                    }while(end > 0 &&nums[end]==nums[end+1]);
                }
            }
        }
        return lists;
    }
}

16.4Sum 大神代码

在以上的基础上还做了一层优化

public List<List<Integer>> fourSum(int[] nums, int target) {
		ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
		int len = nums.length;
		if (nums == null || len < 4)
			return res;

		Arrays.sort(nums);

		int max = nums[len - 1];
		if (4 * nums[0] > target || 4 * max < target)
			return res;

		int i, z;
		for (i = 0; i < len; i++) {
			z = nums[i];
			if (i > 0 && z == nums[i - 1])// avoid duplicate
				continue;
			if (z + 3 * max < target) // z is too small
				continue;
			if (4 * z > target) // z is too large
				break;
			if (4 * z == target) { // z is the boundary
				if (i + 3 < len && nums[i + 3] == z)
					res.add(Arrays.asList(z, z, z, z));
				break;
			}

			threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
		}

		return res;
	}

	/*
	 * Find all possible distinguished three numbers adding up to the target
	 * in sorted array nums[] between indices low and high. If there are,
	 * add all of them into the ArrayList fourSumList, using
	 * fourSumList.add(Arrays.asList(z1, the three numbers))
	 */
	public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
			int z1) {
		if (low + 1 >= high)
			return;

		int max = nums[high];
		if (3 * nums[low] > target || 3 * max < target)
			return;

		int i, z;
		for (i = low; i < high - 1; i++) {
			z = nums[i];
			if (i > low && z == nums[i - 1]) // avoid duplicate
				continue;
			if (z + 2 * max < target) // z is too small
				continue;

			if (3 * z > target) // z is too large
				break;

			if (3 * z == target) { // z is the boundary
				if (i + 1 < high && nums[i + 2] == z)
					fourSumList.add(Arrays.asList(z1, z, z, z));
				break;
			}

			twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
		}

	}

	/*
	 * Find all possible distinguished two numbers adding up to the target
	 * in sorted array nums[] between indices low and high. If there are,
	 * add all of them into the ArrayList fourSumList, using
	 * fourSumList.add(Arrays.asList(z1, z2, the two numbers))
	 */
	public void twoSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
			int z1, int z2) {

		if (low >= high)
			return;

		if (2 * nums[low] > target || 2 * nums[high] < target)
			return;

		int i = low, j = high, sum, x;
		while (i < j) {
			sum = nums[i] + nums[j];
			if (sum == target) {
				fourSumList.add(Arrays.asList(z1, z2, nums[i], nums[j]));

				x = nums[i];
				while (++i < j && x == nums[i]) // avoid duplicate
					;
				x = nums[j];
				while (i < --j && x == nums[j]) // avoid duplicate
					;
			}
			if (sum < target)
				i++;
			if (sum > target)
				j--;
		}
		return;
	}