欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

two pointers

程序员文章站 2022-03-11 18:24:55
...

two pointers是利用问题本身与序列的特性,

使用两个下标i、j对序列进行扫描(可以同向或反向),

以较低的复杂度解决问题。


例:

给定一个递增的正整数序列和一个正整数M,求序列中的两个不同位置的数a和b,

使它们的和恰好为X,输出所有满足条件的方案。

例如给定序列{1,2,3,4,5,6,7,8,9}和x=5,就存在 1+4=5 和 2+3=5 成立。

解:

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int x = in.nextInt();
		int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		int i = 0, j = a.length - 1;
		while (i < j) {
			if (a[i] + a[j] == x) {
				System.out.println(a[i] + "+" + a[j] + "=" + x);
				i++;
				j--;
			} else if (a[i] + a[j] < x) {
				i++;
			} else {
				j--;
			}
		}
	}
}


例:

序列合并问题

假设有两个递增序列A与B,要求将它们合并为一个递增序列C。

解:

public class Main {

	static void merge(int[] a, int[] b, int[] c) {
		int a_len = a.length;
		int b_len = b.length;
		int i = 0;// 指向a
		int j = 0;// 指向b
		int index = 0;// 指向c
		while (i < a_len && j < b_len) {
			if (a[i] <= b[j]) {
				c[index] = a[i];
				i++;
			} else {
				c[index] = b[j];
				j++;
			}
			index++;
		}
		while (i < a_len) {
			c[index] = a[i];
			index++;
			i++;
		}
		while (j < b_len) {
			c[index] = b[j];
			index++;
			j++;
		}
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int[] a = { 1, 3, 5, 7, 9 };
		int[] b = { 0, 2, 4, 6, 8 };
		int[] c = new int[10];
		merge(a, b, c);
		for (int i = 0; i < c.length; i++)
			System.out.print(c[i] + " ");
	}
}
相关标签: Java