LeetCode_数组_中等题

青旅半醒 2022-12-02 01:10 115阅读 0赞

### 目录 ###

*  \-----------------8.28-----------------------
 *  16、最接近的三数之和
 *  18.四数之和
 *  209、长度最小的子数组
 *  39、组合总和
 *  40、组合总和II
 *  287、寻找重复数

# \-----------------8.28----------------------- #

# 16、最接近的三数之和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center]

class Solution {
        
        public int threeSumClosest(int[] nums, int target) {
        
            Arrays.sort(nums);
            int n = nums.length;
            int best = 10000000;
    
            // 枚举 a
            for (int i = 0; i < n; ++i) {
        
                // 保证和上一次枚举的元素不相等
                if (i > 0 && nums[i] == nums[i - 1]) {
        
                    continue;
                }
                // 使用双指针枚举 b 和 c
                int j = i + 1, k = n - 1;
                while (j < k) {
        
                    int sum = nums[i] + nums[j] + nums[k];
                    // 如果和为 target 直接返回答案
                    if (sum == target) {
        
                        return target;
                    }
                    // 根据差值的绝对值来更新答案
                    if (Math.abs(sum - target) < Math.abs(best - target)) {
        
                        best = sum;
                    }
                    if (sum > target) {
        
                        // 如果和大于 target，移动 c 对应的指针
                        int k0 = k - 1;
                        // 移动到下一个不相等的元素
                        while (j < k0 && nums[k0] == nums[k]) {
        
                            --k0;
                        }
                        k = k0;
                    } else {
        
                        // 如果和小于 target，移动 b 对应的指针
                        int j0 = j + 1;
                        // 移动到下一个不相等的元素
                        while (j0 < k && nums[j0] == nums[j]) {
        
                            ++j0;
                        }
                        j = j0;
                    }
                }
            }
            return best;
        }
    }

# 18.四数之和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 1]

class Solution {
        
        public List<List<Integer>> fourSum(int[] nums,int target){
        
            /*定义一个返回值*/
            List<List<Integer>> result=new ArrayList<>();
            /*当数组为null或元素小于4个时，直接返回*/
            if(nums==null||nums.length<4){
        
                return result;
            }
            /*对数组进行从小到大排序*/
            Arrays.sort(nums);
            /*数组长度*/
            int length=nums.length;
            /*定义4个指针k，i，j，h  k从0开始遍历，i从k+1开始遍历，留下j和h，j指向i+1，h指向数组最大值*/
            for(int k=0;k<length-3;k++){
        
                /*当k的值与前面的值相等时忽略*/
                if(k>0&&nums[k]==nums[k-1]){
        
                    continue;
                }
                /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/
                int min1=nums[k]+nums[k+1]+nums[k+2]+nums[k+3];
                if(min1>target){
        
                    break;
                }
                /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
                int max1=nums[k]+nums[length-1]+nums[length-2]+nums[length-3];
                if(max1<target){
        
                    continue;
                }
                /*第二层循环i，初始值指向k+1*/
                for(int i=k+1;i<length-2;i++){
        
                    /*当i的值与前面的值相等时忽略*/
                    if(i>k+1&&nums[i]==nums[i-1]){
        
                        continue;
                    }
                    /*定义指针j指向i+1*/
                    int j=i+1;
                    /*定义指针h指向数组末尾*/
                    int h=length-1;
                    /*获取当前最小值，如果最小值比目标值大，说明后面越来越大的值根本没戏*/
                    int min=nums[k]+nums[i]+nums[j]+nums[j+1];
                    if(min>target){
        
                        break;
                    }
                    /*获取当前最大值，如果最大值比目标值小，说明后面越来越小的值根本没戏，忽略*/
                    int max=nums[k]+nums[i]+nums[h]+nums[h-1];
                    if(max<target){
        
                        continue;
                    }
                    /*开始j指针和h指针的表演，计算当前和，如果等于目标值，j++并去重，h--并去重，当当前和大于目标值时h--，当当前和小于目标值时j++*/
                    while (j<h){
        
                        int curr=nums[k]+nums[i]+nums[j]+nums[h];
                        if(curr==target){
        
                            result.add(Arrays.asList(nums[k],nums[i],nums[j],nums[h]));
                            j++;
                            while(j<h&&nums[j]==nums[j-1]){
        
                                j++;
                            }
                            h--;
                            while(j<h&&i<h&&nums[h]==nums[h+1]){
        
                                h--;
                            }
                        }else if(curr>target){
        
                            h--;
                        }else {
        
                           j++;
                        }
                    }
                }
            }
            return result;
        }
    
    }

# 209、长度最小的子数组 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][20200828232101850.png_pic_center]

class Solution {
        
        public int minSubArrayLen(int s, int[] nums) {
        
            int n = nums.length;
            if (n == 0) {
        
                return 0;
            }
    
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
        
                int sum = 0;
                for (int j = i; j < n; j++) {
        
                    sum += nums[j];
                    if (sum >= s) {
        
                        ans = Math.min(ans, j - i + 1);
                        break;
                    }
                }
            }
            
            return ans == Integer.MAX_VALUE ? 0 : ans;
        }
    }

# 39、组合总和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][20200828232436959.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 4]

# 40、组合总和II #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 5]

# 287、寻找重复数 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 6]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/7a8a5f0b92204f16a18219d2bac4da56.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ba9bd0a69355475592f1a3d0eff5e1b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/df6c93ef2de54ffea67b8b06e51a05da.png
[20200828232101850.png_pic_center]: /images/20221123/bc4536c489374cb1ac54d718d69e8cb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/bd502936b68c4a79b29831f67fd787bf.png
[20200828232436959.png_pic_center]: /images/20221123/00e2b86b54a345b1b3f4b31af0a138b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/cbfd3c1bf8784295ae4f5b1c9dc86047.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/759e529324c145a9a1dd1e48cdbf269d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjcyNzQ2_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/f42e798926d44bef943273cadf39e3b3.png