首页 > 编程语言 >【算法】【优选算法】双指针(下)

【算法】【优选算法】双指针(下)

时间:2024-11-06 17:18:27浏览次数:4  
标签:优选 nums int len ++ 算法 right 指针 left

目录


一、611.有效三⻆形的个数

题目链接:611.有效三⻆形的个数
题目描述:

题目解析:

  • 返回能够成三角形的三元组合的个数;
  • 三元组合内容相同,但是是原数组中不同的下标的元素,这样的三元组在这道题中是不相同的,要计数。

1.1 左右指针解法

解题思路:

  • 因为我们能构成三角形的证明是两条最小边的和大于最大边,所以我们先将数组排序。
  • 排序后,我们只需要固定一条边,然后使用左右指针在[0, 最大边)区间中去搜索符合条件的边即可。
  • 固定的一条边必须是最大边,因为固定最大边的时候,要让另两边之和变大和变小只有一种走法(即变大左指针向后,变小右指针向前),如果固定最小边,让两边之差变小有两种走法(变小左指针向后和右指针向前都行)。
  • 当左右指针元素和小于最大边,我们只需要将左指针向后走,让元素和更大即可。
  • 当左右指针元素和大于最大边,现在[左指针,右指针) 中的元素和右指针的元素都可以构成三角形了。直接将其中元素个数添加到ret结果中,然后让右指针向前走,让元素和减小即可。

解题代码:

//时间复杂度O(n^2)
//空间复杂度O(logn)
import java.util.*;
class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ret = 0;
        for(int i = nums.length - 1; i > 0; i--) {
            int left = 0;
            int right = i - 1;
            while(left < right) {
                if(nums[right] + nums[left] > nums[i]) {
                    ret += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
}

1.2 暴力解法

解题思路:
直接使用三次for循环,将每一种构成三角形的可能都枚举出来,然后一一判断是否符合构成三角形的条件即可。但是这种方法时间复杂度过大,会超时。

解题代码:

//时间复杂度O(n^3)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public int triangleNumber(int[] nums) {
        int ret = 0;
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            for(int j = i +1 ; j < n; j++) {
                for(int k = j+1; k < n; k++) {
                    if(nums[i] + nums[j] + nums[k] > 2 * Math.max(nums[i],Math.max(nums[j],nums[k]))) {
                        ret++;
                    }
                }
            }
        }
        return ret;
    }
}

二、LCR 179.查找总价格为目标值的两个商品

题目链接:LCR 179.查找总价格为目标值的两个商品
题目描述:

题目解析:

  • 数组是有序的,只需要找到一组数组中下标不同的两个数的和为target的返回该组合即可。

2.1 左右指针解法

解题思路:

  • 因为数组是有序的,我们可以利用两数的和的单调性来解题。
  • 我们初始左指针指向第一个元素,右指针指向最后一个元素。两个元素的和的单调性具有规律,让和变大让左指针向后移动,让和变小让右指针向前。

解题代码:

//时间复杂度O(n)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public int[] twoSum(int[] price, int target) {
       int left = 0, right = price.length-1; 
        while(left < right) {
            if(price[left] + price[right] > target) right--;
            else if(price[left] + price[right] < target) left++;
            else return new int[]{price[left],price[right]};
        }
        return null;
    }
}

2.2 暴力解法

解题思路:

  • 我们直接使用两层for循环将不同的下标的两个元素的和枚举出来比较即可。
  • 但是时间复杂度过大,会超出时间限制。
    解题代码:
//时间复杂度O(n^2)
//空间复杂度O(1)
import java.util.*;
class Solution {
    public int[] twoSum(int[] price, int target) {
     for(int i = 0; i < price.length; i++) {
        for(int j = 0; j < price.length; j++) {
            if(price[i] + price[j] == target) {
                return new int[]{price[i],price[j]};
            }
        }
     }
     return null;   
    }
}

三、15.三数之和

题目链接:15.三数之和
题目描述:

题目解析:

  • 数组中三个元素和为0,并且要求其中的元素不能重合,对三元组中先后顺序也没有要求。

3.1 左右指针解法

解题思路:

  • 当我们固定了一个数之后,是不是就是求另两个数的和等于这个固定的数的相反值,这就跟上一道题的思路差不多了,其实也跟第一题三角形思路也相似。
  • 这道题给我们的数组是无序的,这样我们固定一个数之后,我们来求另两个数和时,单调性的控制就不是唯一的,所以我们要将数组排序。
  • 我们使用一个for-i循环先固定一个数,然后使用左右指针在[i+1,nums.length-1] 区间中去三数之和等于0的数,然后将三元组放进结果集,并且左右指针同时移动一步;比0小就左指针向后走让和变大;比0大就右指针向前走。
  • 去重思路:
    • 思路一:
      • 在判断元素和前去重,由于我们数组是有序的,那么相同数值的元素肯定是在一起的,那么我们只要判断移动后的元素与前一步每移动时的值是否相同即可,当相同再次移动到不同即可。
      • 但是这里面有细节问题:当我们使用这样的方法的时候,我们是直接将所有相同的直接跳过,所以我们有可能跳过初始值(也就是i == 0 left == i+1 right == nums.length-1),就如数组是这样[2, 2, 3 ,2],当i = 0 时会跳过直接到第三个元素。所有在while循环条件要加上判断是初始值的条件
      • 还有越界风险:所以在while判断的循环中还要将越界风险排除。
      • 还有我们不知道出判断循环的原因是上面是哪个原因哪一个,所以我们在出来判断循环之后,还要判断是否已经越界或者不符合条件,也就是i >= nums.length 和 left >= right。
    • 思路二:
      • 我们在判断和之后去重,只需要考虑越界风险,和相等即可。但是由于在判断和之中,我们要先将i++ 再去去重,去重后已经到了下一个要进循环的元素了, 所以我们for循环中就不要i++了。
  • 小优化:在这道题中是判断和为0,所以我们当nums[i] > 0,后续[i+1,nums.length-1]空间都是正数,不可能还有结果了,直接出循环。

解题代码

//时间复杂度O(n^2)
//空间复杂度O(logn)
写法一:
import java.util.*;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            if(nums[i] > 0) break;
            //对i去重
            while(i != 0 && i < len && nums[i] == nums[i - 1]) i++;
            if(i >= len) break;
           
            int left = i + 1;
            int right = len - 1;
            while(left < right) {
                while(left < right && left != i+1 && nums[left] == nums[left-1]) left++;//对left去重
                while(left < right && right != len-1 && nums[right] == nums[right+1]) right--;//对right去重
                if(left >= right) break;
               
                if(nums[left] + nums[right] < -nums[i]) left++;
                else if(nums[left] + nums[right] > -nums[i]) right--; 
                else ret.add(Arrays.asList(nums[i],nums[left++],nums[right--]));
            }
        }
        return ret;
    }
}

写法二:
import java.util.*;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for(int i = 0; i < len; ) {
            if(nums[i] > 0) break;
            int left = i + 1;
            int right = len - 1;
            while(left < right) {
                if(nums[left] + nums[right] < -nums[i]) left++;
                else if(nums[left] + nums[right] > -nums[i]) right--; 
                else { 
                    ret.add(Arrays.asList(nums[i],nums[left++],nums[right--]));
                    while(left < right && nums[left] == nums[left-1]) left++;//对left去重
                    while(left < right && nums[right] == nums[right+1]) right--;//对right去重
                }
            }
            //对i去重
            i++;
            while(i < len && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }
}

3.2 暴力解法

解题思路:

  • 我们直接使用三层for循环将每一个三元组枚举出来即可。
  • 去重时我们直接使用HashSet这个集合类即可,所以我们要先将nums排序。
  • 但是会超时。
    解题代码:
//时间复杂度O(n^3)
//空间复杂度O(logn)
import java.util.*;
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
         List<List<Integer>> ret = new ArrayList<>();
         Set<List<Integer>> set = new HashSet<>();
         int len = nums.length;
        for(int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {
                for(int k = j+1; k < len; k++) {
                    if(nums[i] + nums[j] + nums[k] == 0) {
                        set.add(Arrays.asList(nums[i],nums[j],nums[k]));
                    }
                }
            }
        }
        ret.addAll(set);

        return ret;
    }
}

四、18.四数之和

题目链接:18.四数之和
题目描述:

题目分析:
跟上面的三数之和,思路一样,代码雷同,只是需要固定两个数即可。

4.1 左右指针解法

解题思路:

  • 思路参考上一道三数之和,两个细节:
  • 这道题有例子是会超过int的最大值的,所以我们需要在计算和的时候使用long来储存。

    解题代码:
//时间复杂度O(n^3)
//空间复杂度O(logn)
写法一:
import java.util.*;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            //对i去重
            while(i < len && i != 0 && nums[i] == nums[i-1]) i++;
            if(i >= len ) break;

            for(int j = i+1; j < len; j++) {
                //对j去重
                while(j < len && j != i+1 && nums[j] == nums[j-1]) j++;
                if(j >= len ) break;

                long newTarget = (long)target - nums[i] - nums[j];
                int left = j + 1;
                int right = len - 1;
                while(left < right) {
                    while(left < right && left != j+1 && nums[left] == nums[left-1]) left++;//对left去重
                    while(left < right && right != len-1 && nums[right] == nums[right+1]) right--;//对right去重
                    if(left >= right) break;

                    long sum = (long)nums[left] + nums[right];
                    if(sum > newTarget) right--;
                    else if(sum < newTarget) left++;
                    else ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));
                }
            }
        }
        return ret;
    }
}
写法二:
import java.util.*;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        int len = nums.length;
        for(int i = 0; i < len;) {
           
            for(int j = i+1; j < len;) {
              

                long newTarget = (long)target - nums[i] - nums[j];
                int left = j + 1;
                int right = len - 1;
                while(left < right) {
                   
                    long sum = (long)nums[left] + nums[right];
                    if(sum > newTarget) right--;
                    else if(sum < newTarget) left++;
                    else {
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--]));
                        while(left < right && nums[left] == nums[left-1]) left++;//对left去重
                        while(left < right && nums[right] == nums[right+1]) right--;//对right去重
                    }
                }
                //对j去重
                j++;
                while(j < len && nums[j] == nums[j-1]) j++;
            }
            i++;
             //对i去重
            while(i < len && nums[i] == nums[i-1]) i++;

        }
        return ret;
    }
}

4.2 暴力解法

解题思路:

  • 4层for循环,HashSet去重。
  • 会超时。

解题代码:

//时间复杂度O(n^4)
//空间复杂度O(logn)
import java.util.*;
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
         Arrays.sort(nums);
         List<List<Integer>> ret = new ArrayList<>();
         Set<List<Integer>> set = new HashSet<>();
         int len = nums.length;
        for(int i = 0; i < len; i++) {
            for(int j = i+1; j < len; j++) {
                for(int k = j+1; k < len; k++) {
                    for(int n = k+1; n < len; n++){
                        if((long)nums[i] + nums[j] + nums[k] + nums[n] == target) {
                            set.add(Arrays.asList(nums[i],nums[j],nums[k],nums[n]));
                        }
                    }
                    
                }
            }
        }
        ret.addAll(set);
        return ret;
    }
}

标签:优选,nums,int,len,++,算法,right,指针,left
From: https://blog.csdn.net/yj20040627/article/details/143357299

相关文章

  • 算法网关视频分析网关室内消防逃生通道占用工厂企业消防安全AI视频智能监管解决方案
    在当前的企业运营中,消防安全管理是保障人员安全和企业资产不受损失的关键环节。然而,传统的消防安全监管方式往往面临着人力资源有限、技术手段不足等问题,导致无法及时有效地发现和处理潜在的火险隐患。为了应对这一挑战,算法网关视频分析网关利用先进的物联网技术,实现了对火灾风险......
  • 摄像机实时接入分析平台视频分析网关越界检测算法:智能安防的精准防控
    在当今的安全防护领域,越界检测技术的重要性日益凸显。作为人工智能视频监控技术的一个关键组成部分,越界检测视频分析网关能够实时、准确地监控,快速识别异常行为并触发警报,保障区域安全,以下是深入解析。一、技术原理与特点视频分析网关越界检测算法基于深度学习和计算机视觉技术......
  • GESP4级考试语法知识(算法概论(三))
    爱因斯坦的阶梯代码://算法1-12#include<iostream>usingnamespacestd;intmain(){intn=1;//n为所设的阶梯数while(!((n%2==1)&&(n%3==2)&&(n%5==4)&&(n%6==5)&&(n%7==0)))n++;//判别是否满足一组同余式cout<<n<<endl;......
  • GESP4级考试语法知识(算法概论(二))
    ......
  • GESP4级考试语法知识(算法概论(一))
    ......
  • Xshell5登录报“找不到匹配的host key 算法“的错误
    Xshell5登录报"找不到匹配的hostkey算法"的错误现象解决方法一:解决方法二 现象xshell5登录欧拉22.03时报错:找不到匹配的hostkey算法解决方法一:1.编辑/etc/ssh/sshd_config,如下所示: #在行尾增加",ecdh-sha2-nistp521",以满足ecdsa公钥方式登录(密钥长度521......
  • 皮带运行状态识别智慧矿山一体机人员乘坐皮带识别针对物的不安全状态的算法保障
    在矿山行业,安全生产始终是最为重要的议题。随着科技的进步,尤其是人工智能和物联网技术的发展,智慧矿山的概念应运而生,旨在通过智能化手段提升矿山的安全管理水平,减少事故发生,保障人员和设备的安全。在这样的背景下,智慧矿山一体机应运而生,它不仅代表了智能化技术在矿山安全管理中......
  • 使用双指针技术去除ArrayList中的重复元素
    技术博客:使用双指针技术去除ArrayList中的重复元素在Java编程中,处理集合数据时,去除重复元素是一个常见的需求。本文将介绍如何使用双指针技术来高效地去除ArrayList中的重复元素,并通过两种不同的方法进行实现。1.问题背景假设我们有一个包含重复元素的ArrayList,例如:ArrayL......
  • 《JVM第8课》垃圾回收算法
    为什么要进行垃圾回收?垃圾是指JVM中没有任何引用指向它的对象,如果不及时清理这些垃圾对象,那么它就会一直占用内存,如果垃圾对象越来越多,就会出现OOM了。要判断对象是否是垃圾对象有两种方式,一、引用计数法。二、可达性分析法。而要清除垃圾对象有三种常用方式,一、标记-清除算......
  • C#SM4加密算法
    1.管理NuGet程序包,搜索BouncyCastle,安装2.代码示例//加密算法:SM4//加密模式:ECB//填充模式:PKCS5Padding//编码类型:UTF-8///<summary>///加密///</summary>///<paramname="plainText"></param>///<par......