双指针(基础算法题)

简介: 双指针

1.合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目。思路:利用system.arraycopy(nums1, int srcPos, nums2, int destPos, int length)将数组合并后将数组进行排序(用Arrays.sort排序)

参数说明:

nums1:源数组
srcPos:源数组要复制的起始位置
nums2:目的数组
destPos:目的数组放置的起始位置
length:复制的长度
————————————————

public class T5 {
   

    public static void main(String[] args) {
   
        // TODO Auto-generated method stub
        Scanner sc=new     Scanner(System.in);
        System.out.println("请输入n的值:");
        int n=sc.nextInt();
        System.out.println("请输入m的值:");
        int m=sc.nextInt();
        int[] num1=new int[n+m];
        int[] num2=new int[m];
        for(int i=0;i<(m+n);i++) {
   
            System.out.println("请输入数组1第"+(i+1)+"个数的值");
            int a=sc.nextInt();
            num1[i]=a;
        }
        for(int i=0;i<m;i++) {
   
            System.out.println("请输入数组2第"+(i+1)+"个数的值");
            int a=sc.nextInt();
            num1[i]=a;
        }

        hebing(num1,m,num2,n);
    }
    public static void hebing(int num1[],int m,int num2[],int n) {
   
        System.arraycopy(num2,0, num1,n,m);
        Arrays.sort(num1);
        System.out.println(num1);
    }
}

2.三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

思路:首先判断数组的长度是否大于3,小于3时返回一个空的数组,当数组长度大于3,对数组进行排序后往下进行。如果三数和等于0,将三个数的值添加到数组中去。判断左界和右界是否和下一位置重复,若重复则往下一个位置移动。
若和大于 0,说明 nums[R] 太大,R 左移
若和小于 0,说明 nums[L] 太小,L 右移
————————————————


public class 三数和 {
   
    public static void main(String[] args) {
   
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] nums=new int[n];
        for(int i=0;i<n;i++) {
   
            System.out.println("请输入你要输入的数组值");
            int a=sc.nextInt();
            nums[i]=a;
        }
        System.out.println(threeSum(nums));

    }

    public static List<List<Integer>> threeSum(int[] nums) {
   
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) {
   
            return res;
        }

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
   
            if (nums[i] > 0) {
   
                return res;
            } else if (i > 0 && nums[i] == nums[i - 1]) {
   
                continue;
            }
            int L = i + 1;
            int R = n - 1;
            while (L < R) {
   
                if (nums[i] + nums[L] + nums[R] == 0) {
   
                    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    while (L < R && nums[L] == nums[L + 1]) {
   
                        L = L + 1;
                    }
                    while (L < R && nums[R] == nums[R - 1]) {
   
                        R = R - 1;
                    }
                    L = L + 1;
                    R = R - 1;
                } else if (nums[i] + nums[L] + nums[R] > 0) {
   
                    R = R - 1;
                } else {
   
                    L = L + 1;
                }

            }
        }
        return res;
    }
相关文章
|
4天前
|
存储 算法 容器
算法:双指针
算法:双指针
13 3
|
4天前
|
算法 前端开发 JavaScript
< 每日算法:一文带你认识 “ 双指针算法 ” >
`双指针`并非指的是一种具体的公式或者范式。而是一种运算思路,用于节省逻辑运算时间的`逻辑思路`!双指针算法通常用于`优化时间复杂度`!
< 每日算法:一文带你认识 “ 双指针算法 ” >
|
4天前
|
算法
优选算法|【双指针】|611.有效三角形的个数
优选算法|【双指针】|611.有效三角形的个数
|
4天前
|
算法
优选算法|【双指针】|202.快乐数
优选算法|【双指针】|202.快乐数
|
4天前
|
算法
优选算法|【双指针】283.移动零
优选算法|【双指针】283.移动零
|
4天前
|
算法
优选算法|【双指针】|1089.复写零
优选算法|【双指针】|1089.复写零
|
4天前
|
算法
【优选算法专栏】专题一:双指针--------1.移动0
【优选算法专栏】专题一:双指针--------1.移动0
19 0
|
4天前
|
算法 C++
双指针算法·两数之和·三数之和
双指针算法·两数之和·三数之和
9 0
|
4天前
|
算法 C++ 容器
day1·算法-双指针
day1·算法-双指针
9 0
|
4天前
|
算法 关系型数据库 MySQL
大厂算法指南:优选算法 ——双指针篇(下)
大厂算法指南:优选算法 ——双指针篇(下)
29 0