首页 > 代码库 > 18. 4Sum

18. 4Sum

2024-09-28 00:34:40   212人阅读

一、描述

　　1、题目

　　　　技术分享

2、题意

　　　　给一个数组，和一个目标数，求满足数组中的4个数的和为目标数的所有组合!

二、解答

　　　　1、思路：

　　　　数组排序后，依次从前向后取一个数 num[i], target - num[i] 即为下标 i 后面 三数之和。再依次遍历 i 后的数，将目标数记为 target - num[i] - num[j]，化为两数之和。最终采用2变量分别指向 j 后一个数与数组最后一个数，相对遍历，查出满足的所有情况!

public List<List<Integer>> fourSum(int[] nums, int target) {
         
         Arrays.sort(nums);
         
         List<List<Integer>> resultList = new ArrayList<List<Integer>>();
         List<Integer> targetList = null;
         int tempTarget = 0, maxLen = nums.length - 1;
         for(int i = 0; i <= maxLen; i++) {
             if(i == 0 || nums[i] != nums[i-1])
             for(int j = i + 1; j <= maxLen; j++) {

                 tempTarget = (target - nums[i] - nums[j]);
                 int low = j+1;
                 int high = maxLen;
                 while(low < high) {
                     if(nums[low] + nums[high] == tempTarget) {
                         targetList = Arrays.asList(nums[i], nums[j], nums[low], nums[high]);
                         resultList.add(targetList);
                         low++;
                         high--;
                     }
                     else if(nums[low] + nums[high] < tempTarget)
                         low++;
                     else
                         high--;
                 }
             }
         }
         List newList = new ArrayList(new HashSet(resultList)); 
         return newList;
     }

　　　　2、改进

　　　　　　查看到大神回答，可以过滤更多的不符合情况，来增加遍历的速度!测试的速度提高了一半多！

public class Solution {
    public  List<List<Integer>> fourSum(int[] nums, int target) {
        
        List<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 z;
        for(int i = 0; i < len; i++) {
            z = nums[i];
            if(i > 0 && z == nums[i-1])
                continue;
            if(z + 3*max < target) 
                continue;
            if(4*z > target)
                break;
            if(4*z == target) {
                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;
    }

    private  void threeSumForFourSum(int[] nums, int target, int low, int high,
            List<List<Integer>> fourSumList, int z) {
        
        if(low + 1 >= high) 
            return;
        int max = nums[high];
        if(3 * nums[low] > target || 3 * max < target)
            return;
        
        int z1;
        for(int i = low; i < high - 1; i++) {
            z1 = nums[i];
            if( i > low && z1 == nums[i-1])
                continue;
            if(z1 + 2*max < target)
                continue;
            if(3*z1 > target)
                break;
            
            if(3 * z1 == target) {
                if(i + 1 < high && nums[i+2] == z1)
                    fourSumList.add(Arrays.asList(z1, z1, z1, z));
                break;
            }
            
            twoSumForFourSum(nums, target - z1, i + 1, high, fourSumList, z1, z);
        }
    }

    private  void twoSumForFourSum(int[] nums, int target, int low, int high,
            List<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])
                    ;
                x = nums[j];
                while(i < --j && x == nums[j]) 
                    ;
            }
            if(sum < target)
                ++i;
            if(sum > target)
                j--;
        }
    }
}

 

三、总结

　　　　在遍历嵌套层次较多的情况下，用 if 判断过滤不符条件，可以明显提高运行速度!

18. 4Sum


联系
我们