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;
}
}
来源:https://www.cnblogs.com/loongnuts/p/17003784.html
本站部分图文来源于网络,如有侵权请联系删除。