欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2021暑假Leetcode刷题——Two Pointers(2)

程序员文章站 2024-02-29 08:20:28
...

5. 3Sum Closest

思路和3Sum很类似。排序后declare一个difference变量,然后照旧外指针遍历从 0 到 length-2 ,外指针右侧左右指针相向移动。内部循环中计算出每次左右指针移动时所指值的和,与target计算差值与difference比较(注意用绝对值)。如果和小于target左指针右移,大于则右指针左移。注意点:外侧i循环终止的条件上可以加一个difference != 0,这样若sum等于target则直接跳出循环。时间复杂度 O(N^2),空间复杂度 O(1)。

Java的码:

public int threeSumClosest(int[] nums, int target) {
        
        if (nums == null || nums.length < 3) {
            return 0;
        }
        
        Arrays.sort(nums);
        int diff = Integer.MAX_VALUE;
        int length = nums.length;
        
        for (int i = 0; i < length - 2 && diff != 0; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            int left = i + 1;
            int right = length - 1;
 
            while (left < right) {
                int sum = nums[left] + nums[right] + nums[i];
                diff = Math.abs(sum - target) < Math.abs(diff) ? sum - target : diff;
                if (sum < target) {
                    ++left;
                } else {
                    --right;
                } 
            }
        }
        return target + diff;
    }

6. 4Sum

思路:外侧两个指针从左开始循环,在右侧剩下的地方进行2Sum,分两个函数进行。

外侧总函数:时间复杂度O(N^3)。

    public List<List<Integer>> fourSum(int[] nums, int target) {
        
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);        //先排序方便去重
        
        //异常检查,包括target过大或过小
        if  (nums == null || nums.length < 4 || nums[0] * 4 > target 
             || target > nums[nums.length - 1] * 4) {
            return result;
        }
        
        //最外侧i去重,与3Sum相似,注意i的范围
        for (int i = 0; i < nums.length - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            
            //j去重,与3Sum相似
            for (int j = i + 1; j < nums.length - 2; ++j) {
                if (j != i + 1 && nums[j] == nums[j - 1]) continue;
                
                //从2Sum返回的结果中每个List加入nums[i]和nums[j]
                for (var set : twoSum(nums, target - nums[i] - nums[j], j + 1)){
                    result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j])));
                    result.get(result.size() - 1).addAll(set);
                }
            }
        }
        return result;
    }

2Sum函数做法:

6.1. HashSet:与Two Sum里第三种方法类似。遍历nums,先检测HashSet中是否存有 target -  nums[i],再将其存入set。注意点:在非空的情况下,每次循环检查List里最后加的一组是不是和nums[i]相同。如此,可以避免重复的两个值被记下,也可以让防止程序忽略自身加和满足target的情况(如target=4,[2,2,2,2,2])。空间复杂度O(N)。

Java的码:

public List<List<Integer>> twoSum(int[] nums, int target, int start) {
    List<List<Integer>> result = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
        
    for (int i = start; i < nums.length; ++i) {
        if (!result.isEmpty() && result.get(result.size() - 1).get(1) == nums[i]) continue;
        int remain = target - nums[i];
        
        if (set.contains(remain)) {
            result.add(Arrays.asList(remain, nums[i]));
        }
        set.add(nums[i]);
    }
    return result;
}

6.2. Two Pointer:思路和3Sum的思路一模一样。左右指针夹逼直到相遇。空间复杂度O(1)。

public List<List<Integer>> twoSum(int[] nums, int target, int start) {
        List<List<Integer>> result = new ArrayList<>();

        int right = nums.length - 1;
        int left = start;
        
        while (left < right) {
            int sum = nums[left] + nums[right];
                
            if ((left != start && nums[left] == nums[left - 1]) || (sum < target)) {
                ++left;
            } else if ((right < nums.length - 1 && nums[right] == nums[right + 1]) 
                       || (sum > target)) {
                --right;
            } else {
                result.add(Arrays.asList(nums[left++], nums[right--]));
            }
        }

        return result;
    }

7. kSum

思路和4Sum一样,分出2Sum函数,然后递归解决前k-2个数字,每次递归往Listli加一个数字。

Java的码:时间复杂度O(N^{k-1})

public List<List<Integer>> kSum(int[] nums, int target, int start, int k) {
    List<List<Integer>> result = new ArrayList<>();
    
    if (start == nums.length || nums[start] * k > target 
        || target > nums[nums.length - 1] * k){
        return result;
    }
        
    if (k == 2) return twoSum(nums, target, start);

    for (int i = start; i < nums.length; ++i) {
        if (i == start || nums[i - 1] != nums[i]) {   //一样的去重方法
            for (var set : kSum(nums, target - nums[i], i + 1, k - 1)) {
                res.add(new ArrayList<>(Arrays.asList(nums[i])));
                res.get(res.size() - 1).addAll(set);
            }
        }
    }           
    return res;
}