美文网首页
[数组]18. 4Sum

[数组]18. 4Sum

作者: Reflection_ | 来源:发表于2018-06-10 00:55 被阅读0次

18. 4Sum
题目大意
给定一个数组,一个target,要求找出所有和为target的四个数的集合,不能重复。

据说还有hashmap法,但效果不如暴力好。

3sum的升级指针法
时间:O(n^3)

左边固定两个指针l1,l2,每次循环+1
根据和target比较大小,动态调整l3、r指针位置

JAVA: 66 ms

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int l1 = 0; l1 < nums.length-3; l1++){
            if(l1 > 0 && nums[l1] == nums[l1-1]){
                continue;
            }
            for(int l2 = l1 +1; l2< nums.length-2; l2++){
                if(l2 > l1+1 && nums[l2] == nums[l2 -1]){ //去重 注意:l2从第2个位置开始才和前一比较
                    continue;
                }
                int l3 = l2+1;
                int r = nums.length-1;
                while(l3 < r){
                    int sum = nums[l1] + nums[l2] + nums[l3] +nums[r];
                    if(sum == target){
                        res.add(Arrays.asList(nums[l1], nums[l2], nums[l3], nums[r]));
                        l3++;
                        r--;
                        while(l3 < r && nums[l3]==nums[l3-1]){ //去重
                            l3++;
                        }
                        while(l3 < r && nums[r] == nums[r+1]){
                            r--;
                        }
                    }else if(sum < target){
                        l3++;
                    }else{
                        r--;
                    }
                }
                    
            }
        }
        return res;
    }
}

改进JAVA 33ms
加两个限制条件 就快了很多

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int l1 = 0; l1 < nums.length-3; l1++){
            if(nums[l1] + nums[l1+1] + nums[l1+2] + nums[l1+3] > target) break;//如果初始已经太大
            if(nums[l1] + nums[nums.length-1] + nums[nums.length-2] + nums[nums.length-3] < target) continue; //第一个元素太小

            if(l1 > 0 && nums[l1] == nums[l1-1]){
                continue;
            }
            for(int l2 = l1 +1; l2< nums.length-2; l2++){
                if(nums[l1] + nums[l2] + nums[l2+1] + nums[l2+2] > target) break; //l2 too large
                if(nums[l1] + nums[l2] + nums[nums.length-1] + nums[nums.length-2] < target) continue; //第一个元素太小

                if(l2 > l1+1 && nums[l2] == nums[l2 -1]){ //去重 注意:l2从第2个位置开始才和前一比较
                    continue;
                }
                int l3 = l2+1;
                int r = nums.length-1;
                while(l3 < r){
                    int sum = nums[l1] + nums[l2] + nums[l3] +nums[r];
                    if(sum == target){
                        res.add(Arrays.asList(nums[l1], nums[l2], nums[l3], nums[r]));
                        l3++;
                        r--;
                        while(l3 < r && nums[l3]==nums[l3-1]){ //去重
                            l3++;
                        }
                        while(l3 < r && nums[r] == nums[r+1]){
                            r--;
                        }
                    }else if(sum < target){
                        l3++;
                    }else{
                        r--;
                    }
                }
                    
            }
        }
        return res;
    }
}

相关文章

  • LeetCode #18 2018-07-28

    18. 4Sum Given an array nums of n integers and an integer...

  • [数组]18. 4Sum

    18. 4Sum题目大意给定一个数组,一个target,要求找出所有和为target的四个数的集合,不能重复。 据...

  • 力扣每日一题:18.四数之和

    18.四数之和 https://leetcode-cn.com/problems/4sum/[https://le...

  • 18.四数之和

    18.四数之和 题目链接:https://leetcode-cn.com/problems/4sum/[https...

  • leetcode 18. 4Sum

    leetcode 18. 4Sum 题目,但是其解题思路可以延伸到 ksum 参考:1 ksum

  • 18. 4Sum

    https://leetcode.com/problems/4sum/description/输入: 数组 和 t...

  • 18. 4Sum

    Given an array nums of n integers and an integer target, ...

  • 18. 4Sum

    Given an array nums of n integers and an integer target, ...

  • 18. 4Sum

    Description Given an array S of n integers, are there ele...

  • 18. 4Sum

    在3Sum基础上,固定第一个数对剩下的数进行3Sum计算,复杂度为O(n^3)

网友评论

      本文标题:[数组]18. 4Sum

      本文链接:https://www.haomeiwen.com/subject/izoxeftx.html