• 欢迎光临~

每日算法之和为S的两个数字

开发技术 开发技术 2022-12-25 次浏览

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;
    }
}
程序员灯塔
转载请注明原文链接:每日算法之和为S的两个数字
喜欢 (0)