JZ57 和为S的两个数字

题目

输入一个升序数组 array 和一个数字S 
  
  
  
  
  ，在数组中查找两个数
  
  
  
  
  
，使得他们的和正好是S
 


 


 


 


 

，如果有多对数字的和等于S 
 
 
 
 
 ，返回任意一组即可
   
   
   
   
   
，如果无法找出这样的数字
 

 

 

 

 
，返回一个空数组即可 
  
  
  
  
  。

方法1 暴力解题

思路

算法实现

两次循环 

 

 

 

 

 ，两个值相加与sum进行比较          ，为true直接break即可

代码

package mid.JZ57和为S的两个数字; import java.util.ArrayList; public class Solution { /** * 暴力计算 * @param array * @param sum * @return * 运行时间 1084ms * 占用内存 28348KB */ private ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) { ArrayList<Integer> res = new ArrayList<>(); if(array.length == 0) return res; for(int i = 0; i < array.length; i++) { for(int j = 0; j < array.length; j++) { if(array[i] + array[j] == sum) { res.add(array[i]); res.add(array[j]); return res; } } } return res; } }

方法2 双指针

思路

算法实现

这道题目还有一个条件是数组是升序序列

 
 

 
 

 
 

 
 

 
 
，在方法一中没有用到
  
  
  
  
  
。这个条件有什么用？

既然数组是有序的









，那我们肯定知道和找到一定程度就不找了                ，我们为什么要从最小的两个数开始相加呢？

我们可以用二分法的思路
 
 
 
 
 
 
 
 
 
 
，从中间开始找
 


 


 


 


 

。

使用双指针指向数组第一个元素和最后一个元素














，然后双指针对撞移动           ，如果两个指针下的和正好等于目标值sum
  
 
  
 
  
 
  
 
  
 
，那我们肯定找到了









，如果和小于sum 
  
  
  
  
  ，说明我们需要找到更大的
  
  
  
  
  
，那只能增加左边的元素
 


 


 


 


 

，如果和大于sum 
 
 
 
 
 ，说明我们需要找更小的
   
   
   
   
   
，只能减小右边的元素 
 
 
 
 
 。

具体做法：

step 1：准备左右双指针分别指向数组首尾元素
   
   
   
   
   
。

step 2：如果两个指针下的和正好等于目标值sum
 

 

 

 

 
，则找到了所求的两个元素
 

 

 

 

 
。

step 3：如果两个指针下的和大于目标值sum 

 

 

 

 

 ，右指针左移；如果两个指针下的和小于目标值sum          ，左指针右移 

 

 

 

 

 。

step 4：当两指针对撞时

 
 

 
 

 
 

 
 

 
 
，还没有找到









，就是数组没有          。

代码

package mid.JZ57和为S的两个数字; import java.util.ArrayList; public class Solution { /** * 双指针 * @param array * @param sum * @return * 运行时间 * 250ms * 占用内存 * 27188KB */ public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> res = new ArrayList<>(); int left = 0, right = array.length - 1; while(left < right) { if (array[left] + array[right] == sum) { res.add(array[left]); res.add(array[right]); return res; } else if (array[left] + array[right] < sum){ left++; } else { right--; } } return res; } }