问题阐述
遇到了一个算法问题, 话说三个数相加等于目标数, 并且时间复杂度为最小. 例如 {1,3,5,9,6,8,7,2,4}, 其中三个数相加等于 15, 找出这些数.
思考: 对于这个问题, 时间复杂度要求最小, 那么只有一层循环来做, 找到三个数的和是目标数, 需要先排序, 然后通过三个指针来进行移动, 比如说 i,j,k,
i=0,j=i+1,k=arr.length-1, 首先要排序, 有了顺序之后就好做了. 若 arr[i]+arr[j]+arr[k] <target 则 j 进行移动, 若 arr[i]+arr[j]+arr[k]> target 则 k 进行移动, 若相等, 则打印出来.
这就是指针的思想. 有了这个想法, 代码就好说了,
代码实现
代码实现如下, 其中也有快排, 如果不知道快排的同学, 可以看下我写的这篇快排文章: https://www.cnblogs.com/lixiaochao/p/10029968.html
- @Test
- public void test(){
- int[] array = {1,3,5,9,6,8,7,2,4};
- sanAdd(array,15);
- }
- /**
- * 三个数相加等于目标数
- * @param array
- * @param target
- */
- private void sanAdd(int[] array,int target){
- if(array == null){
- return;
- }
- // 排序
- quickSort(array);
- // 三个数相加等于 target
- sanshu(array,target);
- }
- /**
- * 快排
- * @param array
- */
- private void quickSort(int[] array){
- int high = array.length-1,low=0;
- subSort(array,high,low);
- for(int i = 0; i<array.length; i++){
- System.out.println(array[i]);
- }
- }
- private int getMiddle(int[] array,int high,int low){
- int key = array[low];
- while (low <high) {
- while (low < high && array[high]>= key){
- high--;
- }
- array[low] = array[high];
- while (low <high && array[low] <= key){
- low++;
- }
- array[high] = array[low];
- }
- array[low] = key;
- return low;
- }
- private void subSort(int[] array,int high,int low){
- if(low>high){
- return;
- }
- int result = getMiddle(array, high, low);
- subSort(array,result - 1,low);
- subSort(array, high,result + 1);
- }
- private void sanshu(int[] array,int target){
- int i = 0,j,k;
- for(i = 0,j=i+1,k = array.length-1; i <array.length && j<array.length && k>=0;){
- int sum = array[i]+array[j]+array[k];
- if(sum <target){
- j++;
- }else if(sum> target){
- k--;
- }else {
- System.out.println("三个数为: i,j,k:"+array[i]+","+array[j]+","+array[k]);
- j++;
- }
- if(j==k){
- // 进入 i 的大循环
- i++;
- j=i+1;
- k = array.length-1;
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2864059.html