【前言】

今天是刷题打卡第43天！

不好意思哈铁汁们，最近这几周要准备考试，博文更新的可能会不及时，但是一有时间笔者都会补上的哦，抱歉哈。

原题：满足条件的两数之和（双指针）

题目描述：

给定一个有序数组（数组是递增的），如数组arr = {1,4,5,7,9}；找两个数之和为12，找到一组即可停止。

【方法一】：

很明显，本题采用暴力求解很简单，直接套用两层循环解决了，不过时间复杂度就得是O(N^2），这是非常低效的。 所以不可取！

暴力代码：

  

   

    

     

    
    

     

      for (i = 0; i < n; i++)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	for (j = 1; j < n; j++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (arr[i] + arr[j] == k)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			printf("%d %d\n", arr[i], arr[j]);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

【方法二】：

本题已经是有序的数组了，所以我们可以采用“对撞的指针”来解决。

思路：

注意哦，本题中 i 和 j 不是无脑++，-- 的哦，有点类似于二分查找的感觉，不信你看。

 代码执行：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int arr[] = { 1,4,5,7,9 };
     
    
   

    

     

    
    

     
	int sz = sizeof(arr) / sizeof(arr[0]);
     
    
   

    

     

    
    

     
	int k = 12;
     
    
   

    

     

    
    

     
	int i = 0;//i从头开始
     
    
   

    

     

    
    

     
	int j = sz - 1;//j从尾开始
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	while (i < j)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (arr[i] + arr[j] < k)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			i++;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else if (arr[i] + arr[j] > k)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			j--;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			printf("%d %d\n", arr[i], arr[j]);
     
    
   

    

     

    
    

     
			break;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

结语

今天是刷题打卡第43天！

加油吧少年。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121800620