代码随想录刷题Day13

18. 四数之和 - 力扣（LeetCode）

这一题类似三数之和，依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了。

if(nums[i]>=0&&nums[i]>target): 如果当前数nums[i]大于等于0且大于目标值target，则后续的数也会更大，不可能再找到满足条件的四元组，因此可以直接跳出循环。  
if(i>0&&nums[i]==nums[i-1]): 如果当前数nums[i]与前一个数相同，则跳过当前数以避免重复的四元组。  
if(nums[k]+nums[i]>=0&&nums[k]+nums[i]>target): 如果当前数nums[k]和nums[i]的和大于等于0且大于目标值target，则后续的数也会更大，不可能再找到满足条件的四元组，因此可以直接跳出循环。  
if(k>i+1&&nums[k]==nums[k-1]): 如果当前数nums[k]与前一个数相同，则跳过当前数以避免重复的四元组

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>=0&&nums[i]>target){
                break;
            }
            if(i>0&&nums[i]==nums[i-1]){
                continue;
            }
            for(int k=i+1;k<nums.length;k++){
                if(nums[k]+nums[i]>=0&&nums[k]+nums[i]>target){
                    break;
                }
                if(k>i+1&&nums[k]==nums[k-1]){
                    continue;
                }
                int left=k+1;
                int right=nums.length-1;
                while(left<right){
                    long sum=(long) nums[i]+nums[k]+nums[left]+nums[right];
                    if(sum>target){
                        right--;
                    }else if(sum<target){
                        left++;
                    }else{
                        result.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
                        while(right>left&&nums[right]==nums[right-1])right--;
                        while(right>left&&nums[left]==nums[left+1])left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;

    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2,2,2,2,2};
        int target = 8;
        List<List<Integer>> results = solution.fourSum(nums, target);
        for (List<Integer> result : results) {
            System.out.println(result);
        }
    }
}

原文地址：https://blog.csdn.net/zw21sjrc/article/details/143661615

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！