【14天高效制胜】-第2天-求和问题

た入场券 2022-08-28 12:40 150阅读 0赞

**目录**

1、三数之和

2、四数之和

--------------------

# 1、三数之和 #

/**
     * 15. 三数之和
     * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     * */

**方法一：暴力求解**

public List<List<Integer>> threeSum1(int[] nums) {
            //方法一：3层暴力循环，太耗时
            int n = nums.length;
            List<Integer> arr;
            List<List<Integer>> res = new ArrayList<>();
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    for(int k=0;k<n;k++){
                        if((nums[i] + nums[j] + nums[k] == 0) && (i!=j) &&(i!=k) && (j!=k)){
                            arr = new ArrayList<>();
                            arr.add(nums[i]);
                            arr.add(nums[j]);
                            arr.add(nums[k]);
                            Collections.sort(arr);
                            if(!res.contains(arr)){
                                res.add(arr);
                            }
                        }
                    }
    
                }
            }
            return res;
        }

**方法二：单层循环 + 双指针（二层循环）**

public List<List<Integer>> threeSum2(int[] nums) {
            //方法二：单层循环，双指针
            List<Integer> arr;
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length <=2) return res;
    
            Arrays.sort(nums);
            int n = nums.length;
            for(int i=0;i<n-2;i++){
                if(nums[i] > 0) break;//第一个数大于0，则后续所有组合都不需要考虑了，和肯定>0
                if((i>0) && (nums[i-1] == nums[i])) continue;//当第一个数与前一个组合第一个数相等时，跳过
                int target = -nums[i];
                int left = i+1;
                int right = n-1;
    
                while(left<right){
                    if((nums[left] + nums[right]) == target){
                        arr = new ArrayList<>();
                        arr.add(nums[i]);
                        arr.add(nums[left]);
                        arr.add(nums[right]);
                        res.add(arr);
    
                        left++;
                        right--;
                        while((left<right) && (nums[left] == nums[left-1])){
                            left++;
                        }
                        while((left<right) && (nums[right] == nums[right+1])){
                            right--;
                        }
                    }else if((nums[left] + nums[right]) < target){
                        left++;
                    }else{
                        right--;
                    }
                }
            }
            return res;
        }

# 2、四数之和 #

/**
     * 18. 四数之和
     * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] ：
     *
     * 0 <= a, b, c, d < n
     * a、b、c 和 d 互不相同
     * nums[a] + nums[b] + nums[c] + nums[d] == target
     * 你可以按 任意顺序 返回答案 。
     * */

**方法一：暴力求解**

复杂度：O(n^4)

**方法二：双层循环+双指针（三层循环）**

public List<List<Integer>> fourSum(int[] nums, int target) {
            List<Integer> arr;
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null || nums.length<=3) return res;
    
            Arrays.sort(nums);
            int n = nums.length;
            for(int i=0;i<=n-4;i++){
                if((i>0) && (nums[i] == nums[i-1])) continue;
                if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
                if(nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target) continue;
    
                for(int j=i+1;j<=n-3;j++){
                    if((j>(i+1)) && (nums[j] == nums[j-1])) continue;
                    if(nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
                    if(nums[i] + nums[j] + nums[n-2] + nums[n-1] < target) continue;
                    int left = j+1;
                    int right = n-1;
                    while(left < right){
                        int sum = nums[i] + nums[j] + nums[left] + nums[right];
                        if(sum == target){
                            arr = new ArrayList<>();
                            arr.add(nums[i]);
                            arr.add(nums[j]);
                            arr.add(nums[left]);
                            arr.add(nums[right]);
                            res.add(arr);
                            left++;
                            right--;
                            while((left<right) && (nums[left] == nums[left-1])){
                                left++;
                            }
                            while((left<right) && (nums[right] == nums[right+1])){
                                right--;
                            }
                        }else if(sum < target){
                            left++;
                        }else{
                            right--;
                        }
                    }
                }
            }
            return res;
        }