和为S的两个数字

1. 题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

2. 思路

• 双指针：由于数组有序，那么左右两个指针，一个指向第一个（右移），另一个指向最后一个（左移）

3. 实现

• java

public class 和为S的两个数字
{
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum)
    {
        ArrayList<Integer> res = new ArrayList<>();
        //检查参数
        if (array == null || array.length == 0)
        {
            return res;
        }
        //两个指针一个指向第一个元素，另一个指向最后一个元素，求和。
        int left = 0;
        int right = array.length - 1;
        while (left < right)
        {
            int currentSum = array[left] + array[right];
            if (currentSum == sum)
            {
                res.add(array[left]);
                res.add(array[right]);
                return res;
            }
            //如果比sum大，那么第二个指针左移；

            else if (currentSum > sum)
            {
                right--;
            }
            //如果比sum小，那么第一个指针右移
            else
            {
                left++;
            }

        }

        return res;
    }
}

• go

//时间复杂度：O(n)
//空间复杂度：O(1)
func FindNumbersWithSum(array []int, sum int) []int {
	if len(array) == 0 {
		return nil
	}

	left := 0
	right := len(array) - 1
	data := make([]int, 2)
	for left < right {
		currentSum := array[left] + array[right]
		if currentSum == sum {
			data[0] = array[left]
			data[1] = array[right]
			return data
		} else if currentSum < sum {
			left++
		} else {
			right--
		}
	}

	return nil
}

func twoSum(nums []int, target int) []int {
    left := 0
    right := len(nums)-1
    for left < right {
        sum := nums[left] + nums[right]
        if sum == target {
            return []int{nums[left], nums[right]}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return []int{-1,-1}
}

4. 参考

• 和为S的两个数字_牛客网
• 剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode）