双指针法在很多场景及算法中都有使用 主要应用的算法题如下：
-
一个数组中有奇数也有偶数，将所有奇数放到数组左边，将所有偶数放到数组右边
int[] array = {2, 1, 3, 6, 4, 5, 7, 9};int i = 0;int j = array.lentgh - 1;while (i < j){ while(i时间复杂度O(n)
-
一个数组中既有奇数也有偶数，奇数的下标是奇数，偶数的下标是偶数
int[] array = {1, 2, 3, 6, 4, 8, 7, 9};int even = 0; //偶数int odd = 1; //奇数int end = array.length - 1;while(even <= end && odd <= end){ if((array[end] & 1) == 0){ //如果数组最后一个是偶数 swap(array, even, end); even+=2; }else{ swap(array, odd, end); odd+=2; }}for(int i =0; i时间复杂度O(n)
-
求一个有序数组中和等于8的下标
int[] array = {1, 2, 3, 4, 5, 6 ,7, 8};int i = 0;int j = array.length - 1;while(i < j){ if(array[i] + array[j] == 8){ System.out.println("i="+i+" j="+j); i++; j--; }else if(array[i] + array[j] > 8){ j--; }else{ i++; }}时间复杂度O(n)
-
两个有序数组合并且去重合成新数组
int[] a = {4, 8, 10 ,28};int[] b = {3, 9, 10, 17, 28, 30, 40};int[] c = new int[a.length+b.length];int i = 0; int j = 0; int k = 0;while(i < a.length && j < b.length){ if(a[i] < b[j]){ c[k++] = a[i++]; }else if(a[i] == b[j]){//去重 c[k++] = a[i]; i++; j++; }else{ c[k++] = b[j++]; }}while(i < a.length){ c[k++] = a[i++];}while(j < b.length){ c[k++] = b[j++];}for(int m = 0; m时间复杂度O(n)
-
快速排序
int[] array = {3, 4, 1, 7, 6, 2, 0};sortCore(array, 0, array.length -1);private static void sortCore(int[] array, int startIndex, int endIndex) { if(startIndex > endIndex){ return; } int boundray = boundray(array, startIndex, endIndex); sortCore(array, startIndex, boundray - 1); sortCore(array, boundray + 1, endIndex);}private static int boundray(int[] array, int startIndex, int endIndex) { int standard = array[startIndex]; int leftIndex = startIndex; int rightIndex = endIndex; while(leftIndex < rightIndex){ while(leftIndex < rightIndex && array[rightIndex] >= standard){ rightIndex--; } array[leftIndex] = array[rightIndex]; while(leftIndex < rightIndex && array[leftIndex] <= standard){ leftIndex++; } array[rightIndex] = array[leftIndex]; } array[leftIndex] = standard; return leftIndex;}